首页 > 代码库 > hdoj 2391 Filthy Rich 【DP】

hdoj 2391 Filthy Rich 【DP】

题目大意:有个二维数组,你从(0,0)出发,最终到(n,m), 在这个二维数组中,每个位置dp[i][j]都有一定量的黄金,你可以拾取,问你最多能失去多少,并且,你的方向有下,右, 斜向下三个方向;

策略:就是每一个都加上它的上方向与左方向的最大值,这样到最后就是最大值。详情见代码

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2391

代码:

#include<stdio.h>
#include<string.h>
int dp[1005][1005];
int main()
{
	int t, r, c, i, j, v = 1;
	scanf("%d", &t);
	while(t --){
		scanf("%d%d", &r, &c);
		memset(dp, 0, sizeof(dp));  //初始化
		for(i = 1; i <= r; i ++)
			for(j = 1; j <= c; j ++)
			scanf("%d", &dp[i][j]);
		for(i = 1; i <= r; i ++)  //从dp[1][1]开始
			for(j = 1; j <= c; j ++){
				if(dp[i-1][j] > dp[i][j-1])
				dp[i][j] += dp[i-1][j];
				else
					dp[i][j] += dp[i][j-1];
			}
		/*	for(i = 1; i <= r; i ++){
			for(j = 1; j <= c; j ++)
			printf("%d ", dp[i][j]);*/
			printf("Scenario #%d:\n", v++);
			printf("%d\n", dp[r][c]);
			printf("\n");
		//}
	}
	return 0;
}