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;
}