欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

加拿大国赛CCC2014 S5 题解--zhengjun

程序员文章站 2022-06-02 20:05:45
...

首先,可以爆搜,不过分比较少。

然后,我们可以算出每条边,然后把边按照距离排个序。就可以转换成线性 d p dp dp

f i f_i fi 表示到了第 i i i 条边最多可以拿到几个点心

但是,还有一点要考虑,如果有一坨边的距离都一样,那么应该取走那条边呢。

所以,我们可以另外开一个数组记录一下就可以了

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot,x[2001],y[2001];
struct zj{
    int d,x,y;
    bool operator < (const zj &a)const{
        return d<a.d;
    }
}a[4000001];
int f[2001],fb[2001],fd[2001];
int main(){
    scanf("%d",&n);
    m=n*(n-1)/2;
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]),f[i]=1;
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            a[++tot]=(zj){(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]),i,j};
        }
    }
    sort(a+1,a+1+tot);
    for(int i=1;i<=tot;i++){
        int d=a[i].d,u=a[i].x,v=a[i].y;
        if(d!=fd[u]){
            fd[u]=d;
            fb[u]=f[u];
        }
        if(d!=fd[v]){
            fd[v]=d;
            fb[v]=f[v];
        }
        if(u==0){
            f[u]=max(f[u],fb[v]);
        }
        else{
            f[u]=max(f[u],fb[v]+1);
            f[v]=max(f[v],fb[u]+1);
        }
    }
    printf("%d",f[0]);
    return 0;
}