题解：P4563 [JXOI2018] 守卫

· · 题解

复出之后做的第一道区间 DP。

话说控制欲这么强的嘛。

Solution

区间问题，考虑区间 DP。设 f_{l,r} 表示区间 [l,r] 至少放多少个守卫才能全部看守。

首先可以发现，对于一段区间 [l,r]，r 是必须要放看守的，不然没有地方可以看到 r。

然后画个图，你可以发现，若亭子 k 能被 r 看到，则 (k,h_k) 和 (i,h_i) 的连线斜率，一定随着 k 的增大单调递增。

可以发现上图的红色实线的连到的亭子全都可以被看到，而虚线的亭子 s 和能被看见的亭子 t 会满足 s<t,k_s\ge k_t，这时是看不见的。

设 p_i 为 r 亭子能看到的从左到右第 i 个亭子的编号，那么 [p_i+1,p_{i+1}-1] 这个区间是没办法被 r 观测到的。

那么必须放守卫来看守这一段了。假设我们在一个 p_{i+1} 后面的位置 x 放上守卫，可以使得他观测到这个区间至少一个亭子，那么我们必须要保证 h_x>h_{p_{i+1}}。

这时就出问题了，你会发现 r 到 x 的连线斜率 k_x=\dfrac{h_r-h_x}{r-x}<k_{p_r}=\dfrac{h_r-h_{p_{i+1}}}{r-p_{i+1}}，而 p_{i+1}<x，因此 r 是看不到 p_{i+1} 的，矛盾了。

所以我们得出一个结论：放置守卫的位置不能超过 p_{i+1} 。所以 p_{i+1} 和 p_{i+1}-1 必须选其中一个，不然 p_{i+1}-1 观测不到。

那么转移就很显然了，处理出所有 p_i（假设有 t 个，且设 p_0=l-1），f_{l,r}=\sum\limits_{i=0}^{t}\min\{f_{p_i,p_{i+1}},f_{p_{i},p_{i+1}-1}\}。

于是 O(n^3) DP 即可获得 70 分的好成绩。

考虑优化这个区间 DP。考虑固定右端点 r，倒序枚举左端点 l。因为 r 是固定的，所以之前能够看见的亭子是完全一样的。

所以设 p 为到目前为止 [l,r] 内能被 r 看到的最左的亭子，那么因为我们是倒着扫的，所以我们已经有了 [p+1,r] 的答案，那么：

f_{l,r}\leftarrow\min\{f_{l,p-1},f_{l,p}\}+f_{p+1,r}

所以 DP 就被优化成了 O(n^2) 的。扫的时候同步更新 p 就行。

可以说这题让刚复出的我对最优子结构的理解大大提升，对最优子结构的利用可谓是淋漓尽致。

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

const int N = 5000 + 10;
int n;
ll ans, h[N], f[N][N];

bool can_be_see(int x, int now, int r){//x的斜率比now的斜率小，就可以被看到 
    return (h[r] - h[x]) * 1ll * (r - now) < (h[r] - h[now]) * 1ll * (r - x);
}//斜率公式：(x1 - x2) / (y1 - y2)，不过除法改乘法了而已 

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d", &h[i]);
    for(int r=1;r<=n;r++){
        int p = 0;
        ans ^= (f[r][r] = 1);//这个显然嘛 
        for(int l=r-1;l>=1;l--){
            if(!p || can_be_see(l, p, r))
                p = l;
            f[l][r] = min(f[l][p - 1], f[l][p]) + f[p + 1][r];
            ans ^= f[l][r];
        }
    }
    printf("%lld\n", ans);
    return 0; 
}