题意：中文题；
思路：这个题训练的时候看的不是很懂，当时被两外一个题ka了（不卡也不会做，那个n2的优化窝真的没见过）我们正常得到区间动规是n3的（LRK,K是断点），这个题也和枚举断点类似，只是对于断点的优化，我们调整对于L,R的枚举顺序，使得对于dp[i][j]的子状态都在之前已经被计算过了，我们通过结论可知，一个不可见的区间LR
只能在R或R+1处放置守卫才可以看到R点，那么我们的状态就冲这两个位置进行转移，然后就好了
参考了OI爷得到代码（附上链接 传送门）
代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=5000+7; LL n,h[maxn],dp[maxn][maxn]; bool pre[maxn][maxn]; int main() { scanf("%d",&n); for(LL i=1;i<=n;i++){ scanf("%lld",&h[i]); } for(LL i=1;i<=n;i++){ pre[i][i]=0; int as=0; for(LL j=i-1;j>=1;j--){ if(!as||(h[i]-h[j])*(i-as)<(h[i]-h[as])*(i-j)){ pre[i][j]=1; as=j; } else pre[i][j]=0; } } LL ans=0; for(LL r=1;r<=n;r++){ LL as=1,rr=0; for(LL l=r;l>=1;l--){ if(pre[r][l]){ if(rr){ as+=min(dp[l+1][rr],dp[l+1][rr+1]); rr=0; } } else{ if(!rr)rr=l; dp[l][r]+=min(dp[l][rr],dp[l][rr+1]); } dp[l][r]+=as; ans^=dp[l][r]; } } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/lalalatianlalu/p/9392595.html