https://www.lydsy.com/JudgeOnline/problem.php?id=5324
https://www.luogu.org/problemnew/show/P4563
https://loj.ac/problem/2545
题目见上。
参考：https://blog.csdn.net/dofypxy/article/details/80196942
区间dp，设f[i][j]为[i,j]的答案，see[i][j]为i是否能看到j。
显然see数组可以O(n^2)处理，通过斜率很容易处理。
然后就是O(n^2)处理f，emm很不好想。
思考当你在[i,j]区间内放保镖的时候，j肯定要放一个保镖，然后对于j看不到的地方，我们视为区间[ii,jj]。
我们给出结论：为了覆盖这个区间，我们一定需要在jj或jj+1处放一个保镖。这个结论很容易证明。
于是我们就有了f[i][j]=sigma(min(f[ii][jj],f[ii][jj+1]))+1。这个递推式是O(n^3)的。
但是因为当j固定时，移动i，其转移方程有重合的部分，于是可以O(n^2)处理，具体可以看代码。
#include<cmath> #include<queue> #include<cstdio> #include<cctype> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef double dl; const int N=5010; const int INF=2e9; inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } bool see[N][N]; int n,h[N],f[N][N],len[N]; dl slope(int a,int b){return (dl)(h[a]-h[b])/(a-b); } int main(){n=read();h[0]=INF;for(int i=1;i<=n;i++){h[i]=read();int l,r;see[i][i]=see[i][i-1]=1;dl k=slope(i-1,i);for(int j=i-2;j>=1;j--){while(j&&slope(j,i)>=k){see[i][j--]=0;}k=slope(j,i);see[i][j]=1;}}int ans=0;for(int r=1;r<=n;r++){int s=1,t=0;for(int l=r;l;l--){if(see[r][l]){if(!see[r][l-1])t=l-1;f[l][r]=s;}else{f[l][r]=s+min(f[l][t],f[l][t+1]);if(see[r][l-1])s+=min(f[l][t],f[l][t+1]);}ans^=f[l][r];}}printf("%d\n",ans);return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
