题解

只会蠢蠢的\(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;
}
05-11 20:08