【Tyvj1076】数字三角形 2

2014-05-16
竞赛题解 / 动态规划
TYVJ

描述 Description

数字三角形

要求走到最后 mod 100 最大

输入格式 InputFormat

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

输出格式 OutputFormat

mod 100 最大值。

样例输入 SampleInput

9
97
5 76
22 98 61
20 65 57 41
70 34 78 53 51
33 37 28 26 83 25
9 24 3 79 28 43 32
81 25 76 72 75 32 76 39
13 6 84 94 20 85 12 15 36

样例输出 SampleOutput

99

Tyvj 1076

代码 Code

DP. 布尔数组 f[i,j,k]表示走到位置 (i,j) 时权值和能否为 k，输出最后一行使 k 为真的最大值即可。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[26][26];
bool f[26][26][100];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    scanf("%d",&n);
    memset(f,false,sizeof(f));
    for (i=1;i<=n;i++) for (j=1;j<=i;j++) scanf("%d",&a[i][j]);
    f[1][1][a[1][1]]=true;
    for (i=2;i<=n;i++) for (j=1;j<=i;j++) for (k=0;k<100;k++)
    {
        m=(k+a[i][j])%100;
        f[i][j][m]=f[i][j][m] or f[i-1][j-1][k];
        f[i][j][m]=f[i][j][m] or f[i-1][j][k];
    }
    z=0;
    for (j=1;j<=n;j++) for (k=0;k<100;k++) if (f[n][j][k]) z=max(z,k);
    printf("%d\n",z);
    return 0;
}