P1004 方格取数 (双状态DP&四维DP）

P1004 方格取数 (双状态DP&四维DP）

题目传送门

思路：由于两个路径的最优值会互相影响，所以同时走选择最优方案才是正确解法，这样保证不会将一个数加两遍。若走两遍可能不是最优方案（因为第一次会影响第二次的方案）复杂度O(9^4)还是很小的。因为是滚动数组，所以可以降到三维，但没必要。

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[10][10][10][10],a[10][10];
int main(){
	int n,x,y,v;
	scanf("%d",&n);
		while(scanf("%d%d%d",&x,&y,&v)){
			if(!x&&!y&&!v) break;
			a[x][y]=v;
		}
	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++)
				{		//取四种状态的最大值. 
					int tmp=max({dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]});
					dp[i][j][k][l]=tmp+a[i][j]+a[k][l];
					if(i==k&&j==l) dp[i][j][k][l]-=a[i][j];//去重 
				}
		printf("%d\n",dp[n][n][n][n]);
	return 0;
}