Tyvj P1076 数字三角形2---DP(三维）

时间: 1000ms / 空间: 131072KiB / Java类名: Main

动态规划（DP）

描述

数字三角形
要求走到最后mod 100最大

输入格式

第1行n，表示n行 <=25
第2到n+1行为每个的权值

输出格式

mod 100最大值

测试样例1

输入

2 
1 
99 98

输出

99

解题思路：

 因为是mod 100，所以就可以枚举从0到99这100个数
 用dp[i][j][k]来表示（i，j）这个位置数字k是否走过；
 如果走过记为1，没走过记为0；
 从上到下枚举；
 到最后一行，找出最大值就可以了；

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=100;
int a[30][30];
int dp[30][30][110];///dp[i][j][k]=1表示走过了值为k的点
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&a[i][j]);
    dp[1][1][a[1][1]%mod]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            for(int k=0;k<=99;k++)
            {
                if(dp[i-1][j][k]==1||dp[i-1][j-1][k]==1)
                    dp[i][j][(k+a[i][j])%mod]=1;
            }
    int ans=0;
    for(int i=99;i>=0;i--)
        for(int j=1;j<=n;j++)
        {
            if(dp[n][j][i]==1)
            {
                ans=i;
                break;
            }
        }
    printf("%d\n",ans);
    return 0;
}