POJ 3176 Cow Bowling

POJ 3176 Cow Bowling

题意:

给出一个数字三角形，每个分叉路口可以选择一条道路向下走，获得路上的点的权值。求可以获得的最大权值是多少?

思路:

从上向下走和从下向上走是一样的，为了方便最后统计答案，所以这里直接转化为从下向上走。

定义状态: 我们需要知道当每个位置的权值，所以定义 \(f[i][j]\) 为到达第 \(i\) 行，第 \(j\) 个点的路径上获得的最大值是多少。

转移方程: \(f[i][j] = a[i][j] = max(f[i + 1],f[i + 1]][j + 1])\)

实现:

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 355;
int a[N][N];
int f[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
    }

    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= i; j++)
        {
            f[i][j] = a[i][j];
            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
        }
    }
    printf("%d\n", f[1][1]);
    return 0;
}