ZSTU1362-数字三角形

2019/7/24 8:32:46 人评论 次浏览 分类:学习教程

原文链接:http://www.cnblogs.com/YogurtShen/archive/2012/08/29/2661823.html

http://acmpj.zstu.edu.cn/JudgeOnline/showproblem?problem_id=1362

经典DP教学专用。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 102
using namespace std;
int dp[MAXN][MAXN],a[MAXN][MAXN];
int main(void)
{
    int n,i,j;
    while(scanf("%d",&n),n)
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
           for(j=1;j<=i;j++)
              scanf("%d",&a[i][j]);
        for(j=1;j<=n;j++) 
           dp[n][j]=a[n][j];
        for(i=n-1;i>=1;i--)
           for(j=1;j<=i;j++)
              dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
        printf("%d\n",dp[1][1]);
    }
    return 0;
}

转载于:https://www.cnblogs.com/YogurtShen/archive/2012/08/29/2661823.html

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->