自动搬运

查看原文

来自洛谷，原作者为

	Da_Vinci 庙小妖风大，池浅王八多，人傻常数大

搬运于2025-08-24 23:04:08，当前版本为作者最后更新于2025-03-23 17:56:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

简要题意

给出一个 $n\times m$ 的矩形网格，上面有 $k$ 个洞。A 和 B 两个人轮流推着一个球在网格上移动，每次可以使得球向右或者向下移动一步。当球被推出边界或者推到一个洞时游戏结束，如果被推出边界得分为 $0$，如果被推到一个洞里得分就是这个洞的权值。A 想使得分尽可能小，B 想使游戏得分尽可能大，A 先手，设 $g(x,y)$ 为从 $(x,y)$ 开始游戏最终获得的分数，求 $\displaystyle \sum_{i=1}^n\sum_{j=1}^mg(i,j)$。

$n,m\le 10^9,k \le \min(n\times m,10^5)$。

暴力做法

我们考虑游戏进行的过程，很容易想到一个显然的 DP：

• 设计状态 $dp_{i,j,0/1}$ 表示现在处于点 $(i,j)$，当前是玩家 A 还是 B 进行操作。
• 如果在点 $(i,j)$ 上面有一个权值为 $a_{i,j}$ 的洞，那么 $dp_{i,j,0}\gets a_{i,j}\ ,dp_{i,j,1}\gets a_{i,j}$。
• 如果当前点 $(i,j)$ 上面没有洞，那么 $dp_{i,j,0}\gets \min(dp_{i+1,j,1},dp_{i,j+1,1}),dp_{i,j,1}\gets \max(dp_{i+1,j,0},dp_{i,j+1,0})$。

状态数量为 $O(n\times m)$，转移复杂度为 $O(1)$，总复杂度为 $O(n\times m)$。因为 $n,m$ 都很大，所以这样的 DP 显然无法通过。可以发现状态数量很多，转移复杂度却很小，于是考虑优化 DP 的状态数量。

优化

考虑使用两种颜色给矩形网格进行染色，设 $(i,j)$ 的颜色为 $(i+j)\operatorname{and}1$。此时我们发现同种颜色的格子只会由一个玩家来走，就可以不用 DP 数组的第三维了。

这样操作之后状态数没有改变，但是有助于进行进一步的转化。

此时假设当前的格子轮到 A 来走，而且当前格子的右边和下边都没有洞，那么 DP 的转移式可以这样转化：

$$dp_{i,j}\gets \min(\max(dp_{i+2,j},dp_{i+1,j+1}),\max(dp_{i+1,j+1},dp_{i,j+2})) $$

这可以等价为

$$dp_{i,j}\gets \max(dp_{i+1,j+1},\min(dp_{i,j+2},dp_{i,j+2})) $$

通过这个式子可以发现，一个位于 $(i,j)$ 的洞只能对满足 $dx\ge 0,dy\ge 0,dx+dy\le 2$ 且 $i-dx\ge1,j-dy\ge1$ 的 $(i-dx,j-dy)$ 这 $O(1)$ 个点产生直接影响。而如果不受到某个洞的直接影响，$dp_{i,j}\gets dp_{i+1,j+1}$。

这是一个关键的观察，它启示我们用维护 $f_{x-y}$ 代替维护 $dp_{x,y}$ ，因为 $dp_{i,j}\gets dp_{i+1,j+1}$，而 $i-j=(i+1)-(j+1)$。

所以最终的做法是，我们预处理出那 $k$ 个洞能直接影响到的范围，使用 std::vector 存储并且降序排序。枚举 A 是走颜色为 $0$ 的点还是颜色为 $1$ 的点，遍历 std::vector 里面被洞直接影响到的点，使用 std::map 来维护当前 $x-y$ 对应的 $f$ 以及上一次被更新前的位置 $pos$，每次转移之前统计答案，全部转移进行完之后再统计一遍答案，时间复杂度为 $O(k\log k)$，具体可以参见下面的核心代码：

int n, m, k;
ll res;
map<int, int> dp, pos;
map<pair<int, int>, int> val;
vector<pair<int, int> > v;
inline ll query(int x, int y) {
	if (!dp.count(x - y))return 0;
	return dp[x - y];
}
void calc(bool flag) {
	dp.clear(), pos.clear();
	for (auto [x, y] : v) {
		if (flag == (x + y & 1) && dp.count(x - y)) {
			(res += 1ll * dp[x - y] * (pos[x - y] - x)) %= mod;
		}
		if (val.count(make_pair(x, y))) {
			dp[x - y] = val[make_pair(x, y)];
		} else {
			dp[x - y] = flag == (x + y & 1) ?
			                    min(query(x + 1, y), query(x, y + 1)) :
			                    max(query(x + 1, y), query(x, y + 1));
		}
		pos[x - y] = x;
	}
	for (auto [i, j] : dp) {
		if (flag == (2 * pos[i] - i & 1)) {
			(res += 1ll * min(pos[i], pos[i] - i) * j) %= mod;
		}
	}
}

void solve() {
	fr(n, m, k);
	for (int i = 1; i <= k; i++) {
		int x, y, z;
		fr(x, y, z);
		v.emplace_back(x, y);
		val[make_pair(x, y)] = z;
		for (int dx = 0; dx <= 2; dx++) {
			for (int dy = 0; dx + dy <= 2; dy++) {
				if (x > dx && y > dy) {
					v.emplace_back(x - dx, y - dy);
				}
			}
		}
	}
	sort(v.begin(), v.end(), greater());
	v.erase(unique(v.begin(), v.end()), v.end());
	calc(0);
	calc(1);
	fw((res + mod) % mod), pc('\n');
}