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

· · 题解

非常精妙的一个做法。

简化题意：定义合法区域为 y \in [0,R] 的区域，给定一些在合法区域内的标记点，与一些圆心在合法区域外的，半径为 R 的圆，选择第 i 个圆会产生 c_i 的代价。第一问是最多能覆盖几个标记点；第二问是在保证覆盖标记点最多的情况下，代价的最小值。

首先第一问是非常好做的，明显我们可以选上所有的圆，枚举判断即可，复杂度 O(nm)。

第二问一上来就给人一种 NP 问题的感觉啊！但是因为每个圆的半径固定，所以是有做法的。

有一个比较明显的结论：假设所有圆都在合法区域的一侧（代码中将“一侧”钦定为上侧），则将圆按照圆心的 x 从小到大排序，那么假设第 i 个圆无法覆盖某一个点，那么在 i 之后的圆也永远无法覆盖到这个点（一定存在一种代价最小的方案使得这个结论成立）。

这句话其实也点明了去掉无法覆盖点后，排序圆，排序点后，存在匹配关系使得每个圆所覆盖的点都是一段区间。

另起思路，定义 f_{i,j,k} 为目前处理到第 i 个点，上一个被匹配的上侧圆为 j，上一个被匹配的下侧圆为 k 的最小代价。若 j=0 则表示目前从未匹配过上侧圆，k=0 亦同。

初始化：f_{0,0,0}=0。

答案：\min_{i=0}^{m}\min_{j=0}^{m}f_{n,i,j}。

转移不难，我们考虑枚举一个可以包含 i 点的圆，然后如果这个圆就是上次被匹配的某侧圆，那么本次转移无代价，否则就加上这个圆的代价。

但是一个圆会有被加代价多次的情况啊！你说得对，但是我们的结论保证永远不会出现这种情况，因为你总会发现一段点匹配一个圆后才会换圆，且永远不会把匹配圆换回来（结论是对称的）。

欢迎 ctj，记得把 namespace gza 改掉。

#include<bits/stdc++.h>
using namespace std;
namespace gza{
    #define int long long
    #define pb push_back
    #define MT int TTT=R;while(TTT--)
    #define pc putchar
    #define R read()
    #define fo(i,a,b) for(int i=a;i<=b;i++)
    #define rep(i,a,b) for(int i=a;i>=b;i--)
    #define m1(a,b) memset(a,b,sizeof a)
    namespace IO
    {
        inline int read()
        {
            int x=0;
            char ch=getchar();
            bool f=0;
            while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            if(f) x=-x;
            return x;    
        }
        template<typename T> inline void write(T x)
        {
            if(x<0) pc('-'),x=-x;
            if(x>9) write(x/10);
            pc(x%10+'0');
        }
    };
    using namespace IO;

    #define x first
    #define y second
    const int N=110;
    int n,m,r;
    pair<int,int> a[N];
    bool vis[N];
    struct Node{
        int x,y,c,typ;
        bool operator< (const Node& A)const
        {
            return pair<int,int>({x,y})<pair<int,int>({A.x,A.y});
        }
    }b[N];
    bool check(int i,int j)
    {
        if(j==0) return 1;
        int dx=a[i].x-b[j].x,dy=a[i].y-b[j].y;
        return dx*dx+dy*dy<=r*r;
    }
    int f[N][N][N];
    void main(){
        n=R,m=R,r=R;
        fo(i,1,n) a[i].x=R,a[i].y=R;
        fo(i,1,m) b[i].x=R,b[i].y=R,b[i].c=R;
        fo(i,1,m)
            if(b[i].y>r) b[i].typ=1;
            else b[i].typ=2;
        fo(i,1,n)
        {
            bool flag=0;
            fo(j,1,m) if(check(i,j)) flag=1;
            if(!flag) vis[i]=1;
        }
        int now=0;
        fo(i,1,n) if(!vis[i]) now++,a[now]=a[i];
        sort(a+1,a+now+1);
        write(n=now),puts("");
        m1(f,0x3f),f[0][0][0]=0;
        fo(i,1,n) fo(j,0,m) fo(k,0,m) fo(l,1,m) if(check(i,l))
        {
            if(b[l].typ==1) f[i][l][k]=min(f[i][l][k],f[i-1][j][k]+((j!=l)?b[l].c:0));
            else f[i][j][l]=min(f[i][j][l],f[i-1][j][k]+((k!=l)?b[l].c:0));
        }
        int ans=2e9;
        fo(i,0,m) fo(j,0,m) ans=min(ans,f[n][i][j]);
        write(ans);
    }
}
signed main(){
    gza::main();
}