P3344 [ZJOI2015]幻想乡 Wi-Fi 搭建计划解题报告

解题报告

P3344 [ZJOI2015]幻想乡 Wi-Fi 搭建计划解题报告：

题意

分析

代码

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
const int maxn=105;
int n,m,R,as,bs,ps,ans,sum;
int f[maxn][maxn][maxn],ok[maxn];
struct point{
    int x,y,c;
}p[maxn],w[maxn],above[maxn],below[maxn],place[maxn];
inline int cmp(point a,point b){
    return a.x<b.x;
}
inline int check(point a,point b){
    return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y)<=1ll*R*R;
}
int main(){
    scanf("%d%d%d",&n,&m,&R); 
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    for(int i=1;i<=m;i++){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c),sum+=c;
        w[i].x=x,w[i].y=y,w[i].c=c;
        for(int j=1;j<=n;j++)
            if(check(w[i],p[j]))
                ok[j]=1;
        if(y>R)
            above[++as]=w[i];
        if(y<0)
            below[++bs]=w[i];
    }
    for(int i=1;i<=n;i++)
        if(ok[i])
            place[++ps]=p[i];
    sort(above+1,above+1+as,cmp),sort(below+1,below+1+bs,cmp),sort(place+1,place+1+ps,cmp);
    memset(f,0x3f,sizeof(f));
    ans=sum,f[0][0][0]=0;
    for(int i=1;i<=ps;i++)
        for(int a=0;a<=as;a++)
            for(int b=0;b<=bs;b++){
                if((a>0&&check(above[a],place[i]))||(b>0&&check(below[b],place[i])))
                    f[i][a][b]=min(f[i][a][b],f[i-1][a][b]);
                if(i==ps)
                    ans=min(ans,f[i][a][b]);
                for(int k=a+1;k<=as;k++)
                    if(check(above[k],place[i]))
                        f[i][k][b]=min(f[i][k][b],f[i-1][a][b]+above[k].c);
                for(int k=b+1;k<=bs;k++)
                    if(check(below[k],place[i]))
                        f[i][a][k]=min(f[i][a][k],f[i-1][a][b]+below[k].c);
            }
    printf("%d\n%d\n",ps,ans);
    return 0;
}