这道题让我充分认识了我一点不会 dp。
首先可以预处理一个点能看到的左边的所有点。注意到一个区间一定会选择右端点，设右端点不能看到的所有极长区间为 \([l_1,r_1],[l_2,r_2]\dots[l_k,r_k]\)，区间 \([L,R]\) 的答案即为 \(1+\sum f_{l_i,r_i}\)。。。吗。
上述思路是错的，因为看不到的所有小区间不一定要强制选择右端点，还可能会选择右端点右侧的点，并且一定会选择右端点右侧的第一个点。
因为一定是右侧的第一个点遮盖住了该区间所有的点，否则假设 \(k\) 遮盖住了区间 \([l_i,r_i]\) 且 \(r_i+1\) 不能遮盖该区间。右端点也一定会被 \(k\) 遮盖。
这样就得到了 \(\mathcal O(n^3)\) 的 dp，固定右端点，左端点从右向左扫，随便优化成 \(\mathcal O(n^2)\)。
第一眼很容易想麻烦，想到凸包，单调栈之类的玩意，但是还是要先观察特殊性质啊。
int n,ans,f[5010][5010],a[5010];
bool v[5010][5010];
inline void mian()
{
read(n),ans=n&1;
for(int i=1;i<=n+5;++i)for(int j=i+1;j<=n+5;++j)f[i][j]=INF;
for(int i=1;i<=n;++i)
{
read(a[i]),f[i][i]=1;
db minn=INF;int last=i,val=0;
for(int j=i-1;j>=1;--j)
{
if(1.0*(a[i]-a[j])/(i-j)<minn)
{
minn=1.0*(a[i]-a[j])/(i-j);
val+=min(f[j+1][last],f[j+1][last+1]);
last=j-1;
}
ans^=(f[j][i]=val+min(f[j][last],f[j][last+1]));
}
}
write(ans);
}