本文主要是介绍UVa 1366 - Martian Mining (dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文出自 http://blog.csdn.net/shuangde800
题目链接： 点击打开链接
题目大意
给出n*m网格中每个格子的A矿和B矿数量，A矿必须由右向左运输，B矿必须由下向上运输，管子不能拐弯或者间断。要求收集到的A，B矿总量尽量大。
思路
由题意可知，如果格子（i，j）上选择运输A矿的话，那么i行的1~j就要全部选择A矿。
同理，如果选择B矿，那么第j列上的1～i行要全部选择B矿
所以推出下面的状态转移方程式：
f[i][j][1]表示第i行第j列为右下角顶点的矩形区域内，格子(i,j)上选择运输B矿情况下的最大总和
那么
f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]) + sum{第i行的1～j列的A矿之和}
f[i][j][1] = max(f[i][j-1][0], f[i][j-1][1]) + sum{第j列的1～j行的B矿之和};
最终答案是max{f[n][m][0], f[n][m][1]}
代码：
/**==========================================* This is a solution for ACM/ICPC problem** @problem: UVA 1366 - Martian Mining* @type: dp* @author: shuangde* @blog: blog.csdn.net/shuangde800* @email: zengshuangde@gmail.com*===========================================*/#include#include#include#include#include#include #include using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const double PI = acos(-1.0); const int MAXN = 130; int m, n; int A[510][510], B[510][510]; int sum_row[510][510], sum_col[510][510]; int f[510][510][2]; int main(){ while(~scanf("%d%d", &n, &m) && n+m){ memset(sum_row, 0, sizeof(sum_row)); memset(sum_col, 0, sizeof(sum_col)); for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){ scanf("%d", &A[i][j]); sum_row[i][j] = sum_row[i][j-1]+A[i][j]; } for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){ scanf("%d", &B[i][j]); sum_col[i][j] = sum_col[i-1][j]+B[i][j]; } memset(f, 0, sizeof(f)); for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){ f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]) + sum_row[i][j]; f[i][j][1] = max(f[i][j-1][0], f[i][j-1][1]) + sum_col[i][j]; } printf("%d\n", max(f[n][m][0], f[n][m][1])); } return 0; } 这篇关于UVa 1366 - Martian Mining (dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
