学步园

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=102;
int dp[maxn][maxn];
int arr[maxn][maxn];

int main()
{
    int n,i,j;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;++i)
            for(j=1;j<=i;++j)
                scanf("%d",&arr[i][j]);
        memset(dp,0,sizeof(dp));
        dp[1][1]=arr[1][1];
        for(i=2;i<=n;++i)
        {
            dp[i][1]=arr[i][1]+dp[i-1][1];
            for(j=2;j<=i-1;++j)
            {
                dp[i][j]=arr[i][j]+ max(dp[i-1][j-1],dp[i-1][j]);
            }
            dp[i][i]=arr[i][i]+dp[i-1][i-1];
        }
        int ans=-1;
        for(i=1;i<=n;++i)
        if(dp[n][i]>ans)
        ans=dp[n][i];
        printf("%d\n",ans);
    }
    return 0;
}

随便在poj的online status 看ac的题目 然后做。。

第一个就看到这个了 在lrj的第一本白书 dp专题讲的第一道题。

挺水的

对于三角形中节点 上曾有两个节点可以走到它 看从哪个节点走到 的值大就行了 最左边和最右边单独处理。只有一个节点可以走到