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

题目:

数字三角形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;
}

 

上一篇:1076 Wifi密码 (15 分)


下一篇:PTA(Basic Level) Practice-1076 Wifi密码