P4563 [JXOI2018] 守卫 题解
不愧是九条可怜的 \(\text{JXOI}\),只能说确实是道好题。
假设当前我们在求 \([l,r]\),我们不难发现 \(r\) 端点一定要放保镖,于是考虑 \(r\) 保镖的最大监视范围 \([x,r]\)。由题意得到对于 \([x,r]\) 中的每个 \(p_1,p_2,\cdots,p_k\),要求斜率 \(t(p_i,r)\le t(p_{i+1},r)\),那么容易得到在 \(p\in[x+1,r-1]\) 处放保镖一定不如在 \(p-1\) 处放置保镖优。
考虑 \(x-1\) 能被谁保护。我们将 \(x-1\) 和 \(r\) 连线 \(l\) 发现 \(x\) 在 \(l\) 以上,\(p\in[x+1,r-1]\) 都在 \(l\) 以下,那么 \(p>x\) 都无法保护 \(x\)。于是 \(x\) 和 \(x-1\) 一定有一个亭子放保镖,记这个亭子为 \(q\),此时我们惊奇地发现这个子问题的答案变为了 \([l,q]\) 的答案,具有最优子结构性质。那么我们正序枚举 \(r\),倒序枚举每个 \(l\),容易写出区间 dp 的式子来。
题目的关键是能发现 \(r\) 端点一定要放保镖的性质并加以利用。
代码:
#include <bits/stdc++.h>
#define N 5005
using namespace std;
int n;
int a[N];
int ans;
int dp[N][N];
double st(int x, int y) {
return (a[y] - a[x]) * 1.0 / (y - x);
}
int chk(int l, int x, int r) {
return st(x, r) > st(l, r);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int r = 1; r <= n; r++) {
dp[r][r] = 1;
ans ^= 1;
int x = 0, sm = 1;
for (int l = r - 1; l >= 1; l--) {
if (x == 0 || chk(l, x, r))
sm += min(dp[l + 1][x - 1], dp[l + 1][x]), x = l;
dp[l][r] = sm + min(dp[l][x], dp[l][x - 1]);
ans ^= dp[l][r];
}
}
cout << ans << "\n";
return 0;
}
标签:P4563,保镖,int,题解,JXOI2018,dp
From: https://www.cnblogs.com/Rock-N-Roll/p/18406871