题目大意：有一段$n(nleqslant5 imes10^3)$个点的折线，特殊点可以覆盖它以及它左边的它可以“看见”的点（“看见”指连线没有其他东西阻挡）。定义$f_{l,r}$为区间$[l,r]$最少需要的特殊点个数，求：$sumlimits_{l=1}^nsumlimits_{r=l}^nf_{l,r}$
题解：可以用斜率来判断是否可以看见。发现$r$一定要设一个关键点，而若一个极大区间$[l',r']$在$r$处看不见，那么一定要在$r'$或$r'+1$处设一个关键点，所以$f_{l,r}=1+sumlimits_{l',r'}min{f_{l',r'},f_{l',r'+1}}$（$l',r'$即为上文说的极大看不见的区间）
但这样复杂度是$O(n^3)$，不能承受，发现固定了$r$后（固定$l$也行），那些看不见的区间是重复的，可以后缀处理（固定$l$就是前缀）。
卡点：开始$naive$的以为贪心就行了（原以为直接贪心选择$r'+1$即可，然后发现一个斜率降低的折线就挂了）
C++ Code：
#include <algorithm>
#include <cstdio>
#define maxn 5010
const double inf = 1e9;
int n, ans;
int h[maxn], f[maxn][maxn];
inline double slope(int l, int r) {
if (l == r) return inf;
return (h[r] - h[l]) / static_cast<double> (r - l);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", h + i);
for (int r = 1, sum, now; r <= n; ++r) {
ans ^= (sum = f[r][r] = 1);
now = r;
for (int l = r - 1; l; --l) {
if (slope(l, r) < slope(now, r)) {
sum += std::min(f[l + 1][now - 1], f[l + 1][now]);
now = l;
}
ans ^= (f[l][r] = sum + std::min(f[l][now - 1], f[l][now]));
}
}
printf("%d
", ans);
return 0;
}