UVA1366 Martian Mining 题解

这个题可以用动态规划解决。
令\(sbe_{i,j}\) 为第 \(j\) 列 \(1\) 至 \(i\) 个格子 \(BE\) 矿总和，令\(snw_{i,j}\) 为第 \(i\) 行 \(1\) 至 \(j\) 个格子 \(NEW\) 矿总和。
\(dp_{i,j,0}\) 表示为以第（\(i\)，\(j\)）为右下角，第（\(i\)，\(j\)）号格子建立 \(BE\) 矿管道的最大采矿量。
\(dp_{i,j,1}\) 表示为以第（\(i\)，\(j\)）为右下角，第（\(i\)，\(j\)）号格子建立 \(NEW\) 矿管道的最大采矿量。

不难得到以下转移方程：
\(dp_{i,j,1}=\max(dp_{i-1,j,0},dp_{i-1,j,1})+sbe_{i,j}\)。
\(dp_{i,j,0}=\max(dp_{i,j-1,0},dp_{i,j-1,1})+snw_{i,j}\)。

最终输出：\(\max(dp_{n,m,0},dp_{n,m,1})\)。
时间复杂度：\(O(n \times m)\)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,m,b[505][505],nw[505][505],sbe[505][505],snw[505][505],dp[505][505][2],ans1,ans2;
bool bk[505][505];
int main(){
	while(cin>>n>>m&&n&&m){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&b[i][j]); 
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&nw[i][j]); 
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				sbe[i][j]=sbe[i][j-1]+b[i][j];
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				snw[i][j]=snw[i-1][j]+nw[i][j];
			}
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				dp[i][j][1]=max(dp[i-1][j][0],dp[i-1][j][1])+sbe[i][j];
				dp[i][j][0]=max(dp[i][j-1][0],dp[i][j-1][1])+snw[i][j];
			}
		cout<<max(dp[n][m][1],dp[n][m][0])<<endl;
	}
	
	return 0;
}