题解 | Cow Pinball-牛客假日团队赛F题

The cows are playing that cool Japanese 'pinball' game called Pachinko. You've probably seen it, you drop a ball in the top and it hits nails on the way down, veering just a little left or right, until the ball comes out the bottom.
This pachinko game is special: the ball always hits the top nail of the R rows of nails (1 <= R <= 25) and then will hit either the right or left nail underneath that. From there, the ball can hit the next nail that's just a bit lower and to the left or right of the second nail, and so on. The ball never veers too far (i.e., more than 1/2 nail away) from the nail it just hit.
This game also has scoring that's unique: you get points for each little nail you hit on the way down. The cows want to maximize their score on this machine. What is the best score they can achieve?

输入描述:

输入

输出

数字三角形DP：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a[50][50];

int main()
{
    ll maxn=0;
    int r;
    cin>>r;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
            scanf("%lld",&a[i][j]);
        }
    }

    for(int i=r-1;i>=1;i--)//行数
    {
        for(int j=1;j<=i;j++)//列数
        {
           a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
        }
     }
   printf("%lld",a[1][1]);
}

来源：旺 崽