备战2023蓝桥国赛-传纸条

题目描述：


解析：
这道题想了我好久，一开始我是想假如只走一条路线，从(1,1)走到（m,n），这种问题该怎么解决呢？针对这种问题我是设了dp[k][i][j]表示走了k步到达(i,j)的好心程度之和的最大值，然后根据这个来写出转移方程来计算。后面就想有两条路线该怎么办？而且第二条路线是从(m,n)走到(1,1)，只能往左或往上走，仔细想想其实就是从(1,1)走到(m,n),于是题意就变成从(1,1)到(m,n)有两条路线，这两条路线之和要是最大的，且不能有重合的地方。
想到这我就不知道后面该怎么写了。。。
看了题解后才知道，这时可以设dp[x1][y1][x2][y2]表示一条路线从(1,1)走到(x1,y1)，另一条路线从(1,1)走到(x2,y2)的情况下和的最大值，50的4次方，时间复杂度也可以过，但这还可以再优化下，时间复杂度还可以低些，其实我们需要知道的信息不需要那么多，我们只需知道两条路线当前横纵坐标之和以及横坐标，就可以推出纵坐标，而且我们可以假设两条路线是同时走的，故我们可以设dp[k][i][j]表示两条路线同时走，一条路线从(1,1)走到(i,k-i)，另一条路线从(1,1)走到(j,k-j)的情况下和的最大值，k表示第一条路线的终点的横坐标为i,第二条路线的终点的横坐标为j的情况下的终点的横纵坐标之和，由于是同时走两条路线的k是相等的。
按照最后一步两个人的走法分成四种情况：

两个人同时向右走，最大分值是 f[k - 1, i, j] + score(k, i, j)；
第一个人向右走，第二个人向下走，最大分值是 f[k - 1, i, j - 1] + score(k, i, j)；
第一个人向下走，第二个人向右走，最大分值是 f[k - 1, i - 1, j] + score(k, i, j)；
两个人同时向下走，最大分值是 f[k - 1, i - 1, j - 1] + score(k, i, j)；
注意两个人不能走到相同格子，即i和j不能相等。

而且在看完题解之后我发现只走一条路线的情况下不需要三维，二维就够了，设dp[i][j]表示从(1,1)到达(i,j)的好心程度之和的最大值，不需要再循环k，因为到达每个格子的步数是固定的，故再循环步数就没有必要了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int dp[2*N][N][N],w[N][N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		cin>>w[i][j];
		
	for(int k=2;k<=n+m;k++)
	{
		for(int i=max(1,k-m);i<=min(n,k-1);i++)
		{
			for(int j=max(1,k-m);j<=min(n,k-1);j++)
			{
				for(int a=0;a<=1;a++)
				{
					for(int b=0;b<=1;b++)
					{
						int t=w[i][k-i];
						if(i != j || k == n+m)//i==j时也有可能要进入，就是当k==n+m的情况
						{
							t+=w[j][k-j];
							dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-a][j-b]+t);
							
						}
					}
				}
			}
		}
	}
	cout<<dp[n+m][n][n];
	return 0;
}