首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。