数字三角形W(加强版) codevs 2189

2189 数字三角形W

时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold

题目描述 Description

数字三角形
要求走到最后mod 100最大
输入描述 Input Description

第1行n，表示n行
第2到n+1行为每个的权值
输出描述 Output Description

mod 100最大值
样例输入 Sample Input

2
1
99 98
样例输出 Sample Output

99
数据范围及提示 Data Size & Hint

n<=25

此题显然用普通的动归思想不可做，因为答案要mod100，所以在原先的基础上加一重状态。dp[i][j][k]定义为在（ij）这个位置k数是否能被累加到，是一个布尔数组。
状态转移方程： dp[i][j][k]=dp[i+1][j][((k-a[i][j])%100+100)%100] || dp[i+1][j+1][((k-a[i][j])%100+100)%100];
((k-a[i][j])%100+100)%100这样取mod防止出现负数。

#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
int n,dp[maxn][maxn][105],a[maxn][maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=100;j++)
            dp[n][i][j]=(a[n][i]==j);
    for(int i=n-1;i>=1;i--)
        for(int j=1;j<=i;j++)
            for(int k=1;k<=100;k++){
                    dp[i][j][k]=
                    dp[i+1][j][((k-a[i][j])%100+100)%100] 
                ||  dp[i+1][j+1][((k-a[i][j])%100+100)%100];
            }
    for(int i=99;i>=0;i--){
        if(dp[1][1][i]){
            printf("%d",i);
            break;
        }
    }
}