LOJ2545 「JXOI2018」守卫

题目大意

有 \(n\) 座山，第 \(i\) 座山是从 \((i, 0)\) 到 \((i, h_i)\) 的线段。称从第 \(i\) 座山能看到第 \(j\) 座山，当且仅当 \(i\geq j\) 且不存在 \(i < k < j\) 使得 \((j, h_j)\) 到 \((i, h_i)\) 的连线经过了第 \(k\) 座山（恰好交于一点也算经过）。

对一段区间 \([l, r]\) (\(1\leq l\leq r\leq n\))，你希望在其中选出最少数量的山，使得 \([l, r]\) 中每座山都能被至少一座选出的山看到。最少需要选出的山的数量，即为这段区间的花费。

求所有区间的花费的异或和。

数据范围：\(1\leq n\leq 5000\)，\(1\leq h_i\leq 10^9\)。

本题题解

记区间 \([l, r]\) 的花费为 \(f(l, r)\)。

枚举右端点 \(r\)。

首先，位置 \(r\) 必须被选出来，否则没有其它位置能看到它。

选出 \(r\) 后，考虑哪些位置能被 \(r\) 看见。对 \(1\leq i < r\)，设 \(s_i\) 表示点 \((i, h_i)\) 到 \((r,h_r)\) 的斜率，即 \(s_i = \frac{h_r - h_i}{r - i}\)。则位置 \(i\) 能被 \(r\) 看见，当且仅当 \(\forall i < j < r: s_i < s_j\)。这是因为如果存在 \(s_j\leq s_i\)，意味着 \(i\) 会被第 \(j\) 座山挡住。

于是，我们从 \(r\) 到 \(1\) 依次枚举 \(l\)，可以顺便推出 \([l, r]\) 里所有能被 \(r\) 看见的位置，设它们为 \(p_1, p_2, \dots, p_k\) (\(l\leq p_1 < p_2 < \dots < p_k = r\))，另外不妨设 \(p_0 = l - 1\)。那么每一段非空的 \([p_i + 1, p_{i + 1} - 1]\) (\(0\leq i < k\))，是 \(r\) 看不见的。更准确地说，\(p_{i + 1}\) 后面的位置都看不见它们。所以它们只能靠自己被看见（在内部解决）。因此，解决 \([p_i + 1, p_{i + 1} - 1]\) 这段的花费就是：\(\min\{f(p_{i} + 1, p_{i + 1} - 1), f(p_{i} + 1, p_{i + 1})\}\)。

于是我们得到：

\[f(l, r) = \sum_{i = 0}^{k - 1}\min\{f(p_{i} + 1, p_{i + 1} - 1), f(p_{i} + 1, p_{i + 1})\} \]

这样朴素转移是 \(\mathcal{O}(n^3)\) 的。

它很容易优化。发现除了第一段（\([l, p_1 - 1]\)）的长度在变化，其它每段从产生起就是固定的。所以可以用一个变量记录后面每段的花费之和。另外，不难发现这个变量就等于 \(f(p_1 + 1, r)\)，所以甚至不需要记录，直接这样转移即可：

\[f(l, r) = \min\{f(l, p_1 - 1), f(l, p_1)\} + f(p_1 + 1, r) \]

时间复杂度 \(\mathcal{O}(n^2)\)。

总结

本题如果往凸包、单调栈等复杂的方向想，就被误导了。

在一开始，要注意分析题目本身的性质。比如我们抓住了关键的一条：位置 \(r\) 必被选出。顺着这个思路，看哪些点是能被 \(r\) 看见的。进一步发现大区间可以直接从小区间转移过来。于是自然而然就得到了上述的 DP 做法。

参考代码

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

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 5000;
int n, h[MAXN + 5];
int dp[MAXN + 5][MAXN + 5];

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> h[i];
	int ans = 0;
	for (int r = 1; r <= n; ++r) {
		ans ^= (dp[r][r] = 1);
		int p = 0;
		for (int l = r - 1; l >= 1; --l) {
			if (!p || (ll)(h[r] - h[l]) * (r - p) < (ll)(h[r] - h[p]) * (r - l)) {
				p = l;
			}
			dp[l][r] = min(dp[l][p], dp[l][p - 1]) + dp[p + 1][r];
			ans ^= dp[l][r];
		}
	}
	cout << ans << endl;
	return 0;
}