P11086 [ROI 2019] 机器人高尔夫 (Day 2) 题解

简要题意

给出一个 $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)

，具体可以参见下面的核心代码：

CPP

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');
}

P11086 [ROI 2019] 机器人高尔夫 (Day 2) 题解

文章操作

简要题意

暴力做法

优化

相关推荐

评论

P11086 [ROI 2019] 机器人高尔夫 (Day 2) 题解