首页 > 代码库 > lightoj 1036 - A Refining Company(简单dp)
lightoj 1036 - A Refining Company(简单dp)
题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1036
题解:设dp[i][j]表示处理到(i,j)点时的最大值然后转移显然是
dp[i][j] = max(dp[i - 1][j] + asum[i][j] , dp[i][j - 1] + bsum[i][j]);
要么取一整列要么取一整行。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef long long ll;const int M = 5e2 + 10;int ammp[M][M] , bmmp[M][M];ll asum[M][M] , bsum[M][M] , dp[M][M];int main() { int t , Case = 0; scanf("%d" , &t); while(t--) { int n , m; scanf("%d%d" , &n , &m); for(int i = 0 ; i <= n ; i++) ammp[0][i] = 0 , dp[0][i] = 0; for(int j = 0 ; j <= m ; j++) bmmp[j][0] = 0 , dp[j][0] = 0; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) scanf("%d" , &ammp[i][j]) , asum[i][j] = asum[i][j - 1] + ammp[i][j]; } for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) scanf("%d" , &bmmp[i][j]) , bsum[i][j] = bsum[i - 1][j] + bmmp[i][j]; } for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { dp[i][j] = max(dp[i - 1][j] + asum[i][j] , dp[i][j - 1] + bsum[i][j]); } } printf("Case %d: %lld\n" , ++Case , dp[n][m]); } return 0;}
lightoj 1036 - A Refining Company(简单dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。