JXOI2018守卫 区间DP

链接

https://loj.ac/problem/2545

思路

f[i][j]表示i到j区间的最小监视人数
可以预处理出来g[i][j],表示i能否监视到j
(其实预处理的关系不大，完全可以直接判断,不过比较不能加=)
一个区间\([l,r]\)，一定会选r，显然
然后只要管r不能监视的地方\([x,y]\)(多个)
加上f[x][y]或者f[x][y+1]的贡献
%%attack

菜误

题目都没读清楚
一边写一边想，改了又改，调了又调(虽然比sb数据结构调的快)

代码ps:我的数组貌似是反着来的，不过都一样

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const ll N=5e4+7;
ll read() {
    ll x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
ll n,h[N],js[N],q[N];
ll f[5007][5007],g[5007][5007];
int main() {
    // freopen("gurad4.in","r",stdin);
    n=read();
    for(ll i=1;i<=n;++i) h[i]=read();
    for(ll i=1;i<=n;++i) {
        g[i][i-1]=g[i][i]=1;q[1]=i-1;
        for(ll j=i-2,top=1;j>=1;--j) {
            if((h[i]-h[j])*(i-q[top]) < (h[i]-h[q[top]])*(i-j)) {
                q[++top]=j;
                g[i][j]=1;
            }
        }
    }
    // for(int i=1;i<=n;++i) {
    //  for(int j=1;j<=n;++j) {
    //      cout<<g[i][j]<<" ";
    //  }
    //  cout<<"\n";
    // }
    memset(f,0x3f,sizeof(f));
    for(ll i=1;i<=n;++i) {
        f[i][i]=1;
        for(ll j=i-1;j>=1;--j) {
            if(g[i][j]) f[i][j]=f[i][j+1];
            else {
                for(int r=j;!g[i][j]&&j>=1;--j)
                    f[i][j]=f[i][r+1]+min(f[r][j],f[r+1][j]);
                ++j;
            }
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;++i) {
        for(ll j=1;j<=i;++j) {
            ans=ans^f[i][j];    
            // cout<<f[i][j]<<" ";
        }
        // cout<<"\n";
    }
    printf("%lld\n",ans);
    return 0;
}