【JXOI2018】守卫

参考题解：https://blog.csdn.net/dofypxy/article/details/80196942

大致思路就是：区间DP。对于\([l,r]\)的答案，\(r\)肯定要放守卫，然后\(r\)不能看到的一些连续区间\([l_k,r_k]\)是相互独立的。所以\(f_{l,r}=\sum min \{ f_{l_k,r_k},f_{l_k,r_k+1} \}+1\)

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 5005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n;
int h[N];
bool see[N][N];
int f[N][N];
int main() {
    n=Get();
    for(int i=1;i<=n;i++) h[i]=Get();
    for(int i=1;i<n;i++) {
        see[i][i+1]=1;
        int id=i+1;
        for(int j=i+2;j<=n;j++) {
            if(1ll*(h[id]-h[i])*(j-i)<1ll*(h[j]-h[i])*(id-i)) {
                see[i][j]=1;
                id=j;
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            f[i][j]=1e9;
    for(int i=1;i<=n;i++) {
        f[i][i]=1;
        int last=0,sum=0;
        int id=i;
        for(int j=i-1;j>=1;j--) {
            if(see[j][i]) {
                sum+=last;
                id=j;
            }
            last=min(f[j][id],f[j][id-1]);
            f[j][i]=sum+last+1;
        }
    }
    
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            ans^=f[i][j];
    cout<<ans;
    return 0;
}