自动搬运

查看原文

来自洛谷，原作者为

	幽云蓝 a

搬运于2025-08-24 22:33:51，当前版本为作者最后更新于2023-08-24 22:57:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于小波的原 std 被叉爆了所以自己写个题解给大家谢罪了。/kt

首先对恋恋预处理出数组 $f_{i,j}$ 代表从位置 $(i,j)$ 走到她的终点能获得的最大愉悦程度。这里不用考虑觉的影响。

如果假设觉和恋在一起行动（这是经典 trick），那么可以设计 dp 状态。$dp_{i,j,k}$ 代表觉和恋一起走了 $i$ 步，觉有 $j$ 步向左，恋有 $k$ 步向左的最大愉悦程度。但这看起来很不可做。我们考察觉和恋的移动过程。如果觉和恋分开，那么觉会收集愉悦程度为正数的物品，并在她们相遇时把这些物品都给恋。如果觉和恋相遇，那么觉会带走愉悦程度为负数的物品，并把它们在两人不在同一格子时丢弃掉。

麻烦的地方在于，你不知道觉和恋之后会不会相遇/离开，而觉的行动是依赖于这个的。我的思路是不妨首先假设觉一定能把物品带给恋恋/把负数物品带走。然后在觉和恋切换状态（即，相遇变成分离，分离变成相遇）时对答案进行统计。也就是说假设这步后恋一个人走到终点不受觉的影响，然后和 $ans$ 进行 $\text{chkmax}$。

注意特判一下，如果恋的终点可以到觉的终点，那么觉和恋都在恋的终点的这种状态也是合法的，和 $ans$ 也要 $\text{chkmax}$。

附一份代码，大约拍了 600 组。有 hack 可以私我。

#include <bits/stdc++.h>
using namespace std;

int w[310][310];
long long dp[610][310][310];
long long f[310][310];
int e1_x, e1_y, e2_x, e2_y;

int satori_dis;
int koishi_dis;

bool chk(int xa, int ya, int xb, int yb){
	return xa <= e1_x && ya <= e1_y && xb <= e2_x && yb <= e2_y;
}

bool same(int xa, int ya, int xb, int yb){
	return xa == xb && ya == yb;
}

int main(){
//	freopen("1.in","r",stdin);
//    freopen("3.out","w",stdout);
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			cin >> w[i][j];
		}
	cin >> e1_x >> e1_y >> e2_x >> e2_y;
	satori_dis = e1_x + e1_y - 2;
	koishi_dis = e2_x + e2_y - 2;
	int cangt = 0;
	if (satori_dis > koishi_dis && e1_x >= e2_x && e1_y >= e2_y){
		cangt = 1;//shaber xiaobo fnfnfnfnfnfn
	}
	for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) f[i][j] = LONG_LONG_MIN;
	for (int i = e2_x; i >= 1; i--){
		for (int j = e2_y; j >= 1; j--){
			if (i == e2_x){
				if (j == e2_y) f[i][j] = w[i][j];
				else f[i][j] = w[i][j] + f[i][j + 1];
			}
			else{
				if (j == e2_y) f[i][j] = w[i][j] + f[i + 1][j];
				else f[i][j] = w[i][j] + max(f[i][j + 1], f[i + 1][j]);
			}
		}
	}
	for (int i = 0; i <= n + m; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= n; k++){
				dp[i][j][k] = LONG_LONG_MIN;
			}
	dp[0][0][0] = max(0, w[1][1]);
	long long ans = f[1][1];
	for (int i = 0; i <= min(satori_dis, koishi_dis) - 1; i++){
		for (int j = 0; j <= min(i, e1_x - 1); j++)
			for (int k = 0; k <= min(i, e2_x - 1); k++){
				for (int p = 0; p <= 1; p++)
					for (int q = 0; q <= 1; q++){
						int nxa = 1 + j + p;
						int nya = 1 + (i - j) + (1 - p);
						int nxb = 1 + k + q;
						int nyb = 1 + (i - k) + (1 - q);
						if (!chk(nxa, nya, nxb, nyb)) continue;
						int xa = 1 + j;
						int ya = 1 + (i - j);
						int xb = 1 + k;
						int yb = 1 + (i - k);
						if (same(xa, ya, xb, yb) != same(nxa, nya, nxb, nyb)){
							ans = max(ans, dp[i][j][k] + f[nxb][nyb]);
						}
						if (same(nxa, nya, nxb, nyb)){
							dp[i + 1][j + p][k + q] = max(dp[i + 1][j + p][k + q], dp[i][j][k] + max(0, w[nxa][nya]));
						}
						else{
							dp[i + 1][j + p][k + q] = max(dp[i + 1][j + p][k + q], dp[i][j][k] + max(0, w[nxa][nya]) + w[nxb][nyb]);
						}
					}
			}
	}
	if (cangt){
		ans = max(ans, dp[koishi_dis][e2_x - 1][e2_x - 1]);
	}
	cout << ans << endl;
	return 0;
}