P1004 [NOIP2000 提高组] 方格取数 题解

题目链接

P1004 [NOIP2000 提高组] 方格取数

简要思路

注意一下输入可以简化为

while(std::cin>>x>>y>>val&&x){
	//***
}

运用 DP 的思想。

用一个四维的 \(DP\) 数组 \(dp[i][j][k][l]\) 来同时记录两条路径分别走到 \((i,j)\) 和 \((k,l)\) 时的累加最大值。

至于转移方程，每条路径都有从上往下走和从左往右走两种情况，那么两条路径合起来就有四种情况，我们对这四种情况取最大值即可。

即：

dp[i][j][k][l]=std::max(std::max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),std::max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]));

对于当前位置的数值对 DP 数组的贡献，我们可以让其先加上两个路径走到的位置的值，即：

dp[i][j][k][l]+=a[i][j]+a[k][l];

当重合的时候（即 \(i,k\) 相等且 \(j,l\) 相等），由于一个位置的数值只能对答案贡献一次，所以当重合时我们要减去当前的位置的数值。

完整代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

int n;
int x,y,val;
int a[10][10];
int dp[10][10][10][10];//共同处理两条路径

signed main(){
	std::cin>>n;
	while(std::cin>>x>>y>>val&&x!=0)
		a[x][y]=val;//预处理输入矩阵

	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				for(int l=1;l<=n;l++){
					dp[i][j][k][l]=std::max(std::max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),std::max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];//dp 数组的转移
					if(i==k&&j==l)dp[i][j][k][l]-=a[i][j];//重合时减去一个
				}
	std::cout<<dp[n][n][n][n]<<endl;//两条路径分别到达了 (n,n)
	return 0;
}