题解【AcWing275】[NOIP2008]传纸条

题面

首先有一个比较明显的状态设计：设 (dp_{x1,y1,x2,y2}) 表示第一条路线走到 ((x1,y1)) ，第二条路线走到 ((x2,y2)) 的路径上的数的和的最大值。

这个状态设计是可以通过本题的，但其实还有更加简洁的状态设计。

我们设 (dp_{k,x1,x2}) 表示第一条路线和第二条路线分别走了 (k) 步，其中第一条路线走到了 ((x1,k - x1)) ，第二条路线走到了 ((x2, k - x2)) 的路径上的数的和的最大值。

关于 (x1) 和 (x2) 的取值范围：因为 (1 leq x1,x2 leq n) ，且 (1 leq k-x1, k-x2 leq m) ，所以我们可以得出 (max(1,k-m) leq x1,x2 leq min(k-1,n)) 。

由于每一次移动只能向下或向右，因此转移就比较明显了，这里不再赘述。

如果两条路径没有重叠，那么就可以分别加上 ((x1,k-x1)) 和 ((x2,k-x2)) 位置上的数。

注意答案要输出 (dp_{n+m,n,n}) ,不是 (dp_{n+m,n,m}) 。

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define itn int
#define gI gi

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int maxn = 53;

int n, m, a[maxn][maxn], dp[maxn * 2][maxn][maxn], ans = 0;

int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = gi(), m = gi();
	for (int i = 1; i <= n; i+=1)
	{
		for (int j = 1; j <= m; j+=1)
		{
			a[i][j] = gi();
		}
	}
	for (int k = 1; k <= n + m; k+=1)
	{
		for (int x1 = max(1, k - m); x1 <= min(k - 1, n); x1+=1)
		{
			for (int x2 = max(1, k - m); x2 <= min(k - 1, n); x2+=1)
			{
			    //计算出新增加的数的和
				int t = a[x1][k - x1];
				if (x1 != x2) t += a[x2][k - x2];
				//转移状态
				int &v = dp[k][x1][x2];
				v = max(v, dp[k - 1][x1][x2] + t);
				v = max(v, dp[k - 1][x1 - 1][x2] + t);
				v = max(v, dp[k - 1][x1][x2 - 1] + t);
				v = max(v, dp[k - 1][x1 - 1][x2 - 1] + t);
			}
		}
	}
	//输出答案
	printf("%d
", dp[n + m][n][n]);
	return 0;
}