蓝桥杯算法训练VIP-传纸条

题目

题目链接

题解

动态规划。

两个人一个人从左上角向右下角走，另一个人从右下角向左上角走，不允许路径上从同一个位置。我们完全可以转化为两个人都从左上角走，路径上不允许走同一个位置，两个人同时走到右下角的最大值。

四维dp，dp[i][j][p][q]表示第一个人从左上角走到(i, j)，同时第二个人也从左上角走到了(p, q)的最大值，这个最大值就是两条路径之和的最大值。 一般转移方程：dp[i][j][p][q] = max(dp[i-1][j][p-1][q], dp[i-1][j][p][q-1], dp[i][j-1][p-1][q], dp[i][j-1][p][q-1]) + a[p][q] + a[i][j] （可以配合下面的“含义”一起食用） 含义： 首先，这不是完整的转移方程，但是主要的转移方程，我们先把这个方程讲明白； 对于第一个人处于(i, j) 位置，他可以从上面或者左面转移过来，对于第二个人处于(p, q) 位置，他也可以从上面或者左面转移过来。所以说对应着四种情况，①第一个人从上面过来且第二个人从上面过来，②第一个从上面过来且第二个人从左面过来，③第一个从左面过来且第二个人从上面过来，④第一个从左面过来且第二个人从左面过来。现在他们分别到达了(i, j) 位置和(p, q) 位置，因此还需要加上在(i, j) 位置和(p, q) 位置的值，即a[i][j] 和a[p][q] 。

但是，这样并没有满足不允许走同一个位置的限制，因此，我们在遍历四重循环（其实是三重，下面会讲到）的时候，当判断i=j 且p=q 时，说明二者走到同一个位置了，直接continue。 这就出现一个问题，最后二人是都走到了(n, m) 位置，即输出应为dp[n][m][n][m]的值，但是由于我们在上面的判等中，直接continue，导致输出为0。为解决这个问题，我们不直接输出dp[n][m][n][m]的值，而是输出max(dp[n-1][m][n-1][m], dp[n-1][m][n][m-1], dp[n][m-1][n-1][m], dp[n][m-1][n][m-1])，含义为二人都到达(n, m) 位置，还是会出现上述①②③④四种情况，因此我们只要输出一下这四种情况的最大值即可。

至于为什么是三重循环，这是因为dp数组的含义为两个人同时分别到达(i, j) 位置和(p, q) 位置，这就限制了二者步数必须一致。当枚举到三重循环枚举到i、j、p时，i+j就是第一个人走的步数，p+q就是第二个人走的步数，已知二者走的步数相同，且已知i、j、p的值，是不是可以直接求出来q的值，q = i+j-p。注意判断q是否出网格了。

其他的一些方法（可忽略，可以用于加深理解）： 也有很多网上的大佬将到达同一位置的dp值不设置为0，而是在一般转移方程中最后不加a[p][q] + a[i][j]，而是只加a[i][j]或只加a[p][q]，这样最后可以直接输出dp[n][m][n][m]，而不用像我一样还要取个max。同样的，其实在到达同一位置时，直接不加a也是一样的效果。这两种的本质都是其他位置根本就不会由两个人同时到达的同一位置转移过去，因为无论是只加a[i][j]或只加a[p][q]还是直接不加，都绝对不是让最大值尽可能大的最佳转移方案，因此任何一个位置都不可能由这个值转移过去，所以只要加的够小都可以，至于具体原因还需自行理解，我给你讲是讲不明白的。这样唯一的好处就在于可以直接输出dp[n][m][n][m]，但其实这些方法并不能很好的解释题目中“一个同学只会帮一个人的忙”的要求，这也是为什么我推荐我的方式，而不是他们的方式的理由。

代码

#include
using namespace std;
const int N = 55;

int dp[N][N][N][N], a[N][N], n ,m;

int max(int a, int b, int c, int d) { // 重载一下max函数，计算四个数的最大值
	return max(max(a, b), max(c, d));
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i a[i][j];
	
	for(int i = 1;i