菜鸟题解 POJ-3176 Cow Bowling

原题直达

https://vjudge.net/contest/582185#problem/F

题干

原题面
参考翻译

The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:

        7



      3   8



    8   1   0



  2   7   4   4



4   5   2   6   5

Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame.

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output

Line 1: The largest sum achievable using the traversal rules

奶牛打保龄球的时候不会用真正的保龄球。它们每个都取一个数字(范围在0到99之间)，然后像这样排成一个标准的保龄球柱状三角形:

        7



      3   8



    8   1   0



  2   7   4   4



4   5   2   6   5

然后，其他奶牛从三角形的顶端开始穿过三角形，“向下”移动到对角线相邻的两条奶牛中的一条，直到到达“底部”行。这头牛的得分是沿途拜访过的奶牛数量的总和。得分最高的牛赢得了那一局。

给定一个有N (1 <= N <= 350)行的三角形，确定可能达到的最高和。

Input

第1行:单个整数N

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

Output

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

测试案例

Input

Output

题意与思路

这是一道经典的动态规划，从三角形的下方向上遍历，定义数组 dp[][] 用于存储当前最大累计得分，状态转移公式为：

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

求解过程可以参考以下示意图：

题解

#include <iostream>

using namespace std;

const int maxn = 400;

int score[maxn][maxn];
int dp[maxn][maxn];

int main(){
    int N;
    cin>>N;
    for(int i = 0;i < N;i++){
        for(int j = 0;j <= i;j++){
            cin>>score[i][j];
            if(i == N - 1)
                dp[i][j] = score[i][j];
        }
    }

    for(int i = N-2;i >= 0;i--){
        for(int j = 0;j <= i;j++){
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + score[i][j];
        }
    }

    cout<<dp[0][0];
    return 0;
}