题解 P2924 【[USACO08DEC]大栅栏Largest Fence】

Iscream2001 · 2018-02-28 10:34:56 · 题解

首先O（n^4）的dp显然。。 但是n<=250跑不过。。。

考虑换一种方式dp。。。

观察凸包发现从一个点开始，向某一方向沿着边走一圈，边的斜率都是单调的。。。

于是考虑把所有边都连出来，然后按照极角序排序，然后枚举凸包起点dp。。因为保证了边的极角序单调，也就保证了dp顺序的正确性。。

效率是O（n^3），就可以通过此题了

最后是代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#define N 270
#define mod 100000000
#define ept 1e-12
#define LL long long
#define pa pair<int,int>
using namespace std;
int n,cnt,ans;
int f[N];
struct P{
    int l,r;
    double x,y;
}p[N],e[N*N];
bool cmp(P a,P b){
    return atan2(a.x,a.y)<atan2(b.x,b.y);
}
int main(){
    cnt=ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            e[++cnt].l=i;e[cnt].r=j;
            e[cnt].x=p[j].x-p[i].x;
            e[cnt].y=p[j].y-p[i].y;
        }
    sort(e+1,e+1+cnt,cmp);
    for(int i=1;i<=n;i++){
        memset(f,-62,sizeof(f));
        f[i]=0;
        for(int j=1;j<=cnt;j++)
            f[e[j].r]=max(f[e[j].r],f[e[j].l]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}