当前位置:网站首页>P1004 方格取数 (双状态DP&四维DP)

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

2021-08-10 08:02:49 wx6110fa547fd20

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;
} 

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328281