题目:
数字三角形2
从三角形顶端走到最下面一行所经过数字的和sum mod 100要最大
个人感想
最近做了一个特别新颖的DP问题,数字三角形2,网址为:http://www.joyoi.cn/problem/tyvj-1076
大家都知道,数字三角形1,是个特别适合DP入门的DP问题,就是从三角形顶端走到最下面一行所经过数字的和 sum 最大,这个就是普通的DP算法就可以解决。
当做的时候,我原本以为就是加一下取模就行,还不行,就对所有DP数组进行扫描,每一个进行扫描,扫描到最大的就输出,当这也只能过部分样例,后面去网上查一查才发现,这是一个存在性DP问题。
原来这是类似于存在性验证的一类DP,即求出0...99哪个结果可能出现,然后取其中的最大值就是结果。
于是就按照题解的思路,把代码写完了,还是蛮有启发性质的。
解题思路:
设状态 f[i][j][k] 表示到(i,j)的时候能否达到k值,如果可以就==true。从上到下扫过去,对于每个(i,j)只可能从上一行的左边或右边下来,当 f[i][j][k] == true 的时候 ,从上往下 然后 f[i+1][j][(k+a[i+1][j])%100] = true,f[i+1][j+1][(k+a[i+1][j+1]%100)%100]=true. 到最后 进行扫描的时候,肯定是 f[n][][] 在100中选出最大的就行了。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[30][30];
bool f[30][30][100];
int main()
{
int n;
while (~scanf("%d", &n)) {
memset(a, 0, sizeof(a));
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &a[i][j]);
}
}
//变成存在性DP问题,原来这是类似于存在性验证的一类DP,即求出0...99哪个结果可能出现,然后取其中的最大值就是结果。
f[1][1][a[1][1] % 100] = true;
int ans = 0;
for (int i = 1; i <n; i++) { //没有对 i=n的情况 取最大值
for (int j = 1; j <=i; j++) {
for (int k = 0; k < 100; k++) {
if (f[i][j][k]) {
ans = max(ans, k);
f[i + 1][j][(k + a[i+1][j]%100)%100] = true;
f[i + 1][j + 1][(k + a[i + 1][j + 1]%100)%100] = true;
}
}
}
}
for (int j = 1; j <= n; j++) { //对i=n的情况 取最大值
for (int k = 0; k <100; k++) {
if (f[n][j][k]) ans = max(ans, k);
}
}
cout << ans << endl;
}
return 0;
}