P1004 方格取数https://www.luogu.org/problemnew/show/P1004

P1006 传纸条https://www.luogu.org/problemnew/show/P1006

 

方格取数：

设f(i,j,k,l)为从原点分别走两条路径分别到(i,j),(k,l)所取得的和。

状态转移方程：f[i][j][k][l]=max{f[i−1][j][k−1][l],f[i−1][j][k][l−1],f[i][j−1][k−1][l],f[i][j−1][k][l−1]}+a[i][j]+a[k][l]，若(i,j)(k,l)不是同点

若(i,j)(k,l)为同点，f[i][j][k][l]=max{f[i−1][j][k−1][l],f[i−1][j][k][l−1],f[i][j−1][k−1][l],f[i][j−1][k][l−1]}+a[i][j]

递推边界：f(1,1,1,1)=a[1][1].

边界之外：f(_,_,_,_)中_含0则状态值为0.

正确性：若i+j==k+l，则该状态值是正确的，否则不正确，但正确答案不受影响，因为答案所转移的状态都是正确的。

//方格取数递推 
#include<bits/stdc++.h>
using namespace std;

int n,a[10][10],d[10][10][10][10];

int Max(int a,int b,int c,int d)
{
	int x=max(a,b),y=max(c,d);
	return max(x,y);
}

int main()
{
	freopen("input.in","r",stdin);
	int x,y,z;
	cin>>n;
	while((cin>>x>>y>>z)&&x)a[x][y]=z;
	
	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++)
				{
					d[i][j][k][l]=Max(d[i-1][j][k-1][l],d[i-1][j][k][l-1],d[i][j-1][k-1][l],d[i][j-1][k][l-1]);
					d[i][j][k][l]+=((i==k&&j==l)?(a[i][j]):(a[i][j]+a[k][l]));
				}
			}			
		}
	}
	
	cout<<d[n][n][n][n]<<endl;
	return 0;
}
//方格取数-记忆化搜索 
#include<bits/stdc++.h>
using namespace std;

int n,a[10][10],d[10][10][10][10];

int Max(int a,int b,int c,int d)
{
	int x=max(a,b),y=max(c,d);
	return max(x,y);
}

int f(int i,int j,int k,int l)
{
	if(i==0||j==0||k==0||l==0)return 0;
	if(d[i][j][k][l]!=-1)return d[i][j][k][l];
	if(i==1&&j==1&&k==1&&l==1)return d[i][j][k][l]=a[1][1];
	d[i][j][k][l]=Max(f(i-1,j,k-1,l),f(i-1,j,k,l-1),f(i,j-1,k-1,l),f(i,j-1,k,l-1));
	d[i][j][k][l]+=((i==k&&j==l)?(a[i][j]):(a[i][j]+a[k][l]));
	return d[i][j][k][l];
} 

int main()
{
	freopen("input.in","r",stdin);
	int x,y,z;
	cin>>n;
	while((cin>>x>>y>>z)&&x)a[x][y]=z;
	memset(d,-1,sizeof(d));
	
	cout<<f(n,n,n,n)<<endl;
	return 0;
}

传纸条：

设f(i,j,k,l)为从原点到(i,j)(k,l)分别走一条不相交的道路的好心程度之和。

状态转移方程：f[i][j][k][l]=max{f[i−1][j][k−1][l],f[i−1][j][k][l−1],f[i][j−1][k−1][l],f[i][j−1][k][l−1]}+a[i][j]+a[k][l]，若(i,j)(k,l)不是同点

若(i,j)(k,l)为同点，f[i][j][k][l]=0.

递推边界：f(1,1,1,1)=a[1][1].

边界之外：f(_,_,_,_)中_含0则状态值为0.

正确性：若i+j==k+l，则该状态值是正确的，否则不正确，但正确答案不受影响，因为答案所转移的状态都是正确的。

//传纸条递推 四维 
#include<bits/stdc++.h>
using namespace std;

int n,m,a[55][55],d[55][55][55][55];

int Max(int a,int b,int c,int d)
{
	int x=max(a,b),y=max(c,d);
	return max(x,y);
}

void debug()
{
	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++){
                        printf("(%d,%d)&(%d,%d):%d  ",i,j,k,l,d[i][j][k][l]);
                        if(l==n)putchar('\n');
                    }
                }
            }
        }

}


int main()
{
	freopen("input.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=1;k<=n;k++)
			{
				/*
				for(int l=j+1;l<=m;l++)
				{
					d[i][j][k][l]=a[i][j]+a[k][l]+Max(d[i-1][j][k-1][l],d[i-1][j][k][l-1],d[i][j-1][k-1][l],d[i][j-1][k][l-1]);
				}
				*/
				for(int l=1;l<=m;l++)
				{
					if(i==k&&j==l)d[i][j][k][l]=0;
					else d[i][j][k][l]=a[i][j]+a[k][l]+Max(d[i-1][j][k-1][l],d[i-1][j][k][l-1],d[i][j-1][k-1][l],d[i][j-1][k][l-1]);
				}
			}			
		}
	}
	//debug();
	cout<<d[n][m-1][n-1][m]<<endl;
	return 0;
}
//传纸条-三维dp 
#include<bits/stdc++.h>
using namespace std;
 
int m,n,a[55][55],d[105][55][55];

int Max(int a,int b,int c,int d)
{
	int x=max(a,b),y=max(c,d);
	return max(x,y);
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	d[3][1][2]=a[1][2]+a[2][1];
	
	for(int k=4;k<n+m;k++)
	{
		for(int i=1;i<m;i++)
		{
			for(int j=i+1;j<=m;j++)
			{
				if(i<k-n||j>k-1)continue;
				d[k][i][j]=Max(d[k-1][i-1][j-1],d[k-1][i][j],d[k-1][i-1][j],d[k-1][i][j-1]);
				d[k][i][j]+=a[k-i][i]+a[k-j][j];
			}
		}
	}
	cout<<d[n+m-1][m-1][m]<<endl;
	return 0;
}

程序有很多地方需要注意。开始时自己对四维DP的正确性非常怀疑，只好手+脑分析小数据，说是小，3*3的矩阵有3^4=81中状态，费了两天，终于大概想通了一些。