P1004 方格取数

题目大意

在 $n \times n$ 的方格（$n \leqslant 9$）中存在一些正整数，经过格子时获得格子上的数，但只能获得一次。

某人只能向右或向下走，从格子的左上角走到到右下角，共走两次，求最大能取得的数字。

分析

考虑把先走后走转化为两个人同时走，只需要处理遇到两次的值即可。

考虑四维 DP，用 $dp[x_1,y_1,x_2,y_2]$ 表示第一个人走到 $(x_1,y_1)$ 和第二个人走到 $(x_2,y_2)$。

再考虑转移，每一个位置仅可能从其左面或上面转移来，于是可以写出（$x_1 \ne y_1$ 或 $x_2 \ne y_2$ 时）

$$ dp[x_1,y_1,x_2,y_2] = \max\left\{ \begin{matrix} dp[x_1-1,y_1,x_2-1,y_2] \\ dp[x_1,y_1-1,x_2-1,y_2] \\ dp[x_1-1,y_1,x_2,y_2-1] \\ dp[x_1,y_1-1,x_2,y_2-1] \end{matrix}\right\} + a[x_1,y_1] + a[x_2,y_2] $$

当 $x_1=y_1,x_2=y_2$ 时，只加一次即可。到这里 $O(n^4)$ 其实已经可以过题了，但还可以优化。

注意到一些状态是不可达的，因为 $x_1+y_1 = x_2+y_2$，因此存在 $O(n^3)$ 的 DP。

考虑当前已走长度 $h=x_1+y_1=x_2+y_2$，于是可以把两个人的座标表示为 $(x_1,h-x_1)$ 和 $(x_2,h-x_2)$。

于是记状态为 $dp[h,x_1,x_2]$，当 $x_1 \ne x_2$ 时有

$$ dp[h,x_1,x_2] = \max\left\{ \begin{matrix} dp[h-1,x_1,x_2] \\ dp[h-1,x_1,x_2-1] \\ dp[h-1,x_1-1,x_2] \\ dp[h-1,x_1-1,x_2-1] \end{matrix}\right\} + a[x_1,h-x_1] + a[x_2,h-x_2] $$

再注意到可以使用滚动数组，因此有

ll mtx[10][10], dp[10][10];

int main() {
	ll N = rr();
	while (true) {
		ll a = rr(), b = rr(), c = rr();
		if (a + b + c == 0)
			break;
		mtx[a][b] = c;
	}

	for (ll ss = 2; ss <= 2 * N; ss++) {
		ll max_x1 = min(N, ss - 1), min_x1 = max(1ll, ss - N);
		for (ll x1 = max_x1; x1 >= min_x1; x1--) {
			ll max_x2 = min(N, ss - 1), min_x2 = max(1ll, ss - N);
			for (ll x2 = max_x2; x2 >= min_x2; x2--) {
				dp[x1][x2] = max4(
					dp[x1 - 1][x2 - 1],
					dp[x1][x2 - 1],
					dp[x1 - 1][x2],
					dp[x1][x2]
				);
				dp[x1][x2] += mtx[x1][ss - x1] + mtx[x2][ss - x2];
				if (x1 == x2)
					dp[x1][x2] -= mtx[x1][ss - x1];
			}
		}
	}
	printf("%lld\n", dp[N][N]);
	return 0;
}