题解
只会蠢蠢的\(n^3\)……菜啊……
我们发现最右的端点一定会选，看到的点一定是当前能看到的斜率最小的点变得更小一点，记录下这个点，在我们遇到一个看不到的点的时候，然后只用考虑R到它斜率最小的这个点，是被R看到，不放守卫，还是这个点放一个守卫
也就是\(min(f[l][t] + f[t + 1][r],f[l][t - 1] + f[t][r])\)为什么是对的呢，如果我们枚举的中间点在别的位置，这个位置一定能被R看到，视线还会被R看到的斜率最小的这个点挡住，所以是没有必要枚举的
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
//#define ivorysi
#define pb push_back
#define eps 1e-12
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define fi first
#define se second
#define mo 974711
#define MAXN 5005
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 - '0' + c;
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) putchar('-'),x = -x;
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct Point {
int64 x,y;
Point(){};
Point(int64 _x,int64 _y) {
x = _x;y = _y;
}
friend int64 operator * (const Point &a,const Point &b) {
return a.x * b.y - a.y * b.x;
}
friend Point operator - (const Point &a,const Point &b) {
return Point(a.x - b.x,a.y - b.y);
}
friend Point operator + (const Point &a,const Point &b) {
return Point(a.x + b.x,a.y + b.y);
}
}P[MAXN];
int N;
bool vis[MAXN][MAXN];
int f[MAXN][MAXN],ans;
void Solve() {
read(N);int64 h;
for(int i = 1 ; i <= N ; ++i) {
read(h);P[i] = Point(i,h);
}
memset(f,0x3f3f3f3f,sizeof(f));
f[1][1] = 1;ans ^= 1;
for(int r = 2 ; r <= N ; ++r) {
Point T = Point(r,0);int t = r;
f[r][r] = 1;ans ^= 1;
for(int l = r - 1; l >= 1 ; --l) {
if((T - P[r]) * (P[l] - P[r]) < 0) {
T = P[l];t = l;
f[l][r] = f[l + 1][r];
}
else {
f[l][r] = min(f[l][t - 1] + f[t][r],f[l][t] + f[t + 1][r]);
}
ans ^= f[l][r];
}
}
printf("%d\n",ans);
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}