分析
区间DP+九条可怜。
首先发现一条性质：对于一个区间 $[l,r]$ ，显然必须要在 $r$ 处放一个保镖。
设 $f[i][j]$ 表示 $[i,j]$ 的答案。
考虑让右端点从右往左扫，然后设 $p$ 为 $r$ 能看到的最左边的位置， $sum$ 表示 $p$及其右边部分的答案。
容易知道 $p-1$ 的纵坐标必然低于 $p$ ，于是一定要在 $p-1$ 或 $p$ 的地方放一个保镖，容易得到 $f[i][j]=sum+\min\left\{f[i+1][p-1],f[i+1][p]\right\}$。
在扫的过程中，需要同时更新 $p$ 和 $sum$ 。以及边界为 $f[i][i]=1$ 。
最后来考虑怎么判定可见性。容易发现，如果直线 $(i,j)$ 的斜率比直线 $(p,j)$ 的斜率大，那么 $j$ 就能看见 $i$ 。
细节见代码。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=5000+10;
int n,h[N];
int f[N][N];
inline double slope(int i,int j) { return 1.0*(h[i]-h[j])/(i-j); }
inline int check(int p,int i,int j) { return slope(p,j)>slope(i,j); }
int main() {
n=read();
for (re int i=1;i<=n;++i) h[i]=read();
for (re int j=1;j<=n;++j) {
f[j][j]=1; int sum=1,p=0;
for (re int i=j-1;i>=1;--i) {
if (!p||check(p,i,j))
sum+=min(f[i+1][p-1],f[i+1][p]),p=i;
f[i][j]=sum+min(f[i][p-1],f[i][p]);
}
}
int ans=0;
for (re int i=1;i<=n;++i)
for (re int j=i;j<=n;++j)
ans^=f[i][j];
printf("%d\n",ans);
return 0;
}
OrzOrzOrz
切神仙题的聚聚%%%
我考试这题爆0了嘤嘤嘤