【POJ - 3176】牛保龄球 （简单dp）

牛保龄球

直接中文了

Descriptions

奶牛打保龄球时不使用实际的保龄球。它们各自取一个数字（在0..99范围内），然后排成一个标准的保龄球状三角形，如下所示：

然后其他奶牛从其尖端开始穿过三角形并“向下”移动到两个对角相邻的奶牛中的一个，直到到达“底部”行。奶牛的得分是沿途参观的奶牛数量的总和。得分最高的母牛赢得了那个框架。

给定具有N（1 <= N <= 350）行的三角形，确定可实现的最高可能总和。

input

第1行：单个整数，N

第2行...N + 1：行i + 1包含i个以空格分隔的整数，表示三角形的第i行。

output

第1行：使用遍历规则可实现的最大总和

样本输入

样本输出

Hint

如上所示，通过穿越奶牛可以实现最高分。

 

题目链接

https://vjudge.net/problem/POJ-3176

 

杨辉三角形

从下往上找，从两者选一个最大的去和上面的那个数相加，最后就能得出最大值

 

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 350+5

using namespace std;

int main()

{

    int n;

    int dp[Maxn][Maxn];//三角形

    cin>>n;

    for(int i=; i<=n; i++)//输入

        for(int j=; j<=i; j++)

            cin>>dp[i][j];

    for(int i=n-; i>=; i--)//从小往上找最优解

    {

        for(int j=; j<=i; j++)

            dp[i][j]=max(dp[i+][j],dp[i+][j+])+dp[i][j];

    }

    cout<<dp[][]<<endl;//输出

}