前言

这道题我做了半年qwq

一道非常典型的区间dp
题目要求是从小渊到小轩再回到小渊，那么我们不妨从小渊开始求两条不重合的去小轩的路径。

如图，当我们找到了一条路径后，那么这张图就被分成了两部分，我们的另一条路径只可能存在于其中的一部分中，像这样：

我们可以用$f[x_1][y_1][x_2][y_2]$表示两次传递分别到$(x_1,y_1)$和$(x_2,y_2)$是能够获得的最大好感度。
但是，这个数组的维度太高了，所以我们要对他降维。
怎么降维呢？
~~扔一个三向箔~~
我们可以发现，每当我们走一步，那么x坐标和y坐标之间总会有一个数加$1$。所以，我们可以用k来表示x坐标和y坐标的和，从而通过y坐标来计算出x坐标。由于k对于两条同时处理的路径可以是公共的，所以我们可以用$f[k][y_1][y_2]$来表示当前状态。
于是，我们就可以得到一个状态转移方程了：
$$f[k][i][j]=max(f[k-1][i][j],f[k-1][i-1][j]f[k-1][i][j-1]f[k-1][i-1][j-1])+map[k-i+1][i]+map[k-j+1][j]$$
我们可以来看一下我们到底是通过哪些状态转移到当前状态的：

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define qwq printf("qwq\n");

using namespace std;

int read()
{
	register int x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,m,map[205][205],f[205][205][205]; 

int cmp(int a,int b,int c,int d)
{
	a = max(a,b);
	c = max(c,d);
	return max(a,c);
}

int main()
{
	m = read(); n = read();
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++)
			map[i][j] = read();
	for(int k = 1; k <= m + n; k++)
		for(int i = 1; i <= min(k,n); i++)
			for(int j = i + 1; j <= min(k,n); j++)
				f[k][i][j] = cmp(f[k - 1][i][j],f[k - 1][i - 1][j],f[k - 1][i][j - 1],f[k - 1][i - 1][j - 1]) + map[k - i + 1][i] + map[k - j + 1][j];
	f[n + m][n][n] = max(f[n + m - 1][n][n - 1],f[n + m - 1][n - 1][n]);
	printf("%d\n",f[n + m][n][n]);
    return 0;
}