【LOJ】 #2545. 「JXOI2018」守卫

题解

只会蠢蠢的\(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;

}

巴特西

【LOJ】 #2545. 「JXOI2018」守卫

题解

代码

最新文章

热门文章