这道题让我充分认识了我一点不会 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)$。
第一眼很容易想麻烦，想到凸包，单调栈之类的玩意，但是还是要先观察特殊性质啊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
}