P1004方格取数(四维DP模板题)
题意:
一个矩阵，A从左上角走到右下角，B从右下角走到最下角问AB走过的路径和最大是多少，一个点只能被计算一次
思路：
定义dp[i][j][k][l]为A走到(i , j) B走到 (k , l) 的最大值
那么状态转移方程就为dp[i][j][k][l]=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]) + a[i][j] + a[k][l]
还需注意的是当 i==k && j==l时要减去一次a[i][j]的值，因此重复走一个点只能算一次
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn=10; int a[maxn][maxn],dp[maxn][maxn][maxn][maxn]; int main() { int n,x,y,c; scanf("%d",&n); while(scanf("%d%d%d",&x,&y,&c)&&x&&y&&c) a[x][y]=c; memset(dp,0,sizeof(0)); 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]=max(dp[i-1][j][k-1][l],max(dp[i][j-1][k-1][l],max(dp[i-1][j][k][l-1], dp[i][j-1][k][l-1])))+a[i][j]+a[k][l]; if(i==k&&j==l) dp[i][j][k][l]-=a[i][j]; } } } } cout<<dp[n][n][n][n]<<endl; }
当然还可以降到三维dp[i][j][k]表示走了i步，A走到j行，B走到k行
那么转移方程式为max(dp[i-1][j][k] , dp[i-1][j-1][k-1] , dp[i-1][j-1][k] , dp[i-1][j][k-1])
仍要记得去重
#include<stdio.h> using namespace std; int n;int map[9][9]; int d[18][9][9];int res; int max(int a,int b,int c,int d) { return (((((a>b)?a:b)>c)?((a>b)?a:b):c)>d)?((((a>b)?a:b)>c)?((a>b)?a:b):c):d; } int main() { scanf("%d",&n); while (1) { int x;int y;int val; scanf("%d%d%d",&x,&y,&val); if(x==0&&y==0&&val==0)break; map[x-1][y-1]=val; } d[0][0][0]=map[0][0]; for(int i=0;i<2*n;i++){ for(int j=0;j<=i&&j<n;j++){ for(int k=0;k<=i&&k<n;k++){ if(i==0&&j==0&&k==0)continue; d[i][j][k]=map[j][i-j]+map[k][i-k]+ max(d[i-1][j][k],d[i-1][j-1][k-1],d[i-1][j-1][k],d[i-1][j][k-1]); if(j==k)d[i][j][k]-=map[j][i-j]; } } } res=d[2*(n-1)][n-1][n-1]; printf("%d",res); return 0; }
原文：https://www.cnblogs.com/overrate-wsj/p/12335362.html
