POJ1163DP

淡淡的烟草味﹌ 2022-08-18 00:40 16阅读 0赞

题意和解析，看代码最后部分

#include <iostream>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    
    int main()
    {
        int t,n;
        int dp[105][105];
        int a[105][105];
        //scanf("%d",&t);
        while(scanf("%d",&n)!=EOF)
        {
    
            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++)
                {
                    if(i==n)dp[i][j]=a[i][j];
                    else
                    {
                        dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
                    }
                }
            }
    //        for(int i = 1 ; i <= n ; i++)
    //        {
    //            for(int j = 1 ; j <= i ; j++)
    //            {
    //                printf("%d ",dp[i][j]);
    //            }
    //            printf("\n");
    //        }
            printf("%d\n",dp[1][1]);
        }
        return 0;
    }
    
    /*
    Auther:LIUYAN
    2015.11.30
    数字三角形(POJ1163)
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
    路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
    三角形的行数大于1小于等于100，数字为0 -99
    “人人为我”递推型动归程序
    a(i,j) : 第i行第j个数字(i,j从1开始算)
    dp(i,j) : 从a(i,j)到底边的各条路径中，最佳路径的数字之和。
    问题：求dp(1,1)
    100
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    */