本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-17 21:06:48

难度：$\color{black}\text{NOI/NOI+/CTSC}$

题面：

不需要解释

题目分析：

注意，第 $i$ 号武器被摧毁后第 $i+1$ 号武器就会立即进入攻击状态。炸弹的那个持续引爆5分钟实际上就是说炸弹能摧毁的武器都会立即摧毁，那个5分钟实际上没有用，例如第$1,2,3,4,6$号武器在攻击范围内，那么炸弹将会瞬间摧毁$1,2,3,4$号武器。
可以开个数组 attack[maxn][maxn]，记录第 $j$ 个武器是否在第 $i$ 个炸弹的攻击范围内。这么处理：

for(reg int i=1;i<=n;i++)
{
    for(reg int j=1;j<=m;j++)
    {
        if(k*k>=((zd[i].x-wq[j].x)*(zd[i].x-wq[j].x)+(zd[i].y-wq[j].y)*(zd[i].y-wq[j].y)))\/\/k*k省去开根运算
        {
            attack[i][j]=1;
        }
    }
}

然后跑个dp求解第$i$个武器攻击的情况下从第 $j$ 个武器炸起最大能炸到的武器编号：

for(reg int i=1;i<=n;i++)
{
    for(reg int j=m;j>0;j--)
    {
        if(!attack[i][j])continue;
        max_attack[i][j]=max(j,max_attack[i][j+1]);
    }
}

再跑个dp求解从第 $i$ 个武器炸起炸毁最后一个武器最少需要多少武器

for(reg int i=m;i>0;i--)
{\/\/dp
    for(reg int j=1;j<=n;j++)
    {
        if(!attack[j][i])continue;
        min_zd[i]=min(min_zd[i],min_zd[max_attack[j][i]+1]+1);
    }\/\/当前炸起最远能炸到max_attack[j][i]，加上1就到了下一个炸弹所对应的武器区间。
    \/\/所以min_zd[max_attack[j][i]+1]就是下一个炸弹对应的武器区间炸起所需要的最少炸弹。
    \/\/min_zd[max_attack[j][i]+1]还要加上1是因为要考虑到min_zd[max_attack[j][i]+1]是后面的武器区间，
    \/\/还需要算上当前炸弹。
}

然后定义一个数组wcpd[maxn][maxn]，代表第 $i$ 个武器是否对应第 $j$个 武器区间 再定义一个数组vis[maxn][maxn]，用于匈牙利算法

然后就是dfs了，定义：

void dfs(int x,int qj);\/\/到了第x个武器，分了qj个区间

然后定义一个数组huisu，用于暂时存储

然后从 $x \rightarrow m$枚举武器($i$)，从 $1 \rightarrow n$ 枚举炸弹($j$)，如果武器 $x$ 在当前炸弹的攻击范围内($attack[j][x]==true$)并且当前炸弹从 $x$ 炸起最大能炸到的编号($max_attack[j][x]$) $\ge$ 当前枚举武器编号($i$) ($max_attack[j][x]$ $\ge$ $i$),那么标记上第 $j$ 个武器对应第 $i$个 武器区间（$ wcpd[j][qj+1]=1$）。然后用匈牙利算法看一下当前炸弹是否能匹配上，如果能，那么递归下去即可。最后要注意回溯。这一部分的代码：

bool xylsf(int x)\/\/匈牙利算法
{
    for(int i=1;i<=n;i++)
    {
        if(wcpd[i][x]&&!vis[i])
        {
            vis[i]=1;
            if(!dy[i]||xylsf(dy[i]))
            {
                dy[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
void dfs(int x,int qj)\/\/到了第x个武器，分了qj个区间
{
    if(qj+min_zd[x]>=ans)return;\/\/剪枝
    if(x>m)
    {
        ans=qj;
        return;
    }
    int huisu[maxn];\/\/用于回溯
    for(reg int i=x;i<=m;i++)
    {
        for(reg int j=1;j<=n;j++)
        {
            huisu[j]=dy[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=1;\/\/j控制了qj++的武器区间
            }
        }
        memset(vis,0,sizeof(vis));
        if(xylsf(qj+1))dfs(i+1,qj+1);
        \/\/接下来是回溯
        for(reg int j=1;j<=n;j++)
        {
            dy[j]=huisu[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=0;\/\/j控制了qj++的武器区间
            }
        }
    }
}

题目分析完毕

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
#define reg register
int n,m,k;
const int maxn=105;
bool attack[maxn][maxn];\/\/第i个炸弹是否能炸掉第j个武器
int max_attack[maxn][maxn];\/\/第i个炸弹进行攻击，从第j个武器开始炸能攻击到的最大编号武器
int min_zd[maxn];\/\/从第i个开始炸起，最少要用多少炸弹才能炸掉最后的武器
int ans;
int dy[maxn];\/\/一个炸弹配对了那些
bool wcpd[maxn][maxn];
bool vis[maxn];
struct Wq\/\/武器
{
    int x,y;
}wq[maxn];
struct Zd\/\/炸弹
{
    int x,y;
}zd[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
bool xylsf(int x)\/\/匈牙利算法
{
    for(int i=1;i<=n;i++)
    {
        if(wcpd[i][x]&&!vis[i])
        {
            vis[i]=1;
            if(!dy[i]||xylsf(dy[i]))
            {
                dy[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
void dfs(int x,int qj)\/\/到了第x个武器，分了qj个区间
{
    if(qj+min_zd[x]>=ans)return;\/\/剪枝
    if(x>m)
    {
        ans=qj;
        return;
    }
    int huisu[maxn];\/\/用于回溯
    for(reg int i=x;i<=m;i++)
    {
        for(reg int j=1;j<=n;j++)
        {
            huisu[j]=dy[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=1;\/\/j控制了qj++的武器区间
            }
        }
        memset(vis,0,sizeof(vis));
        if(xylsf(qj+1))dfs(i+1,qj+1);
        \/\/接下来是回溯
        for(reg int j=1;j<=n;j++)
        {
            dy[j]=huisu[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=0;\/\/j控制了qj++的武器区间
            }
        }
    }
}
inline void indata()
{
    m=read();
    n=read();
    k=read();
    for(reg int i=1;i<=m;i++)
    {
        wq[i].x=read();
        wq[i].y=read();
    }
    for(reg int i=1;i<=n;i++)
    {
        zd[i].x=read();
        zd[i].y=read();
    }
}
inline void init()
{
    for(reg int i=1;i<=n;i++)
    {
        for(reg int j=1;j<=m;j++)
        {
            if(k*k>=((zd[i].x-wq[j].x)*(zd[i].x-wq[j].x)+(zd[i].y-wq[j].y)*(zd[i].y-wq[j].y)))\/\/k*k省去开根运算
            {
                attack[i][j]=1;
            }
        }
    }
    for(reg int i=1;i<=n;i++)
    {
        for(reg int j=m;j>0;j--)
        {
            if(!attack[i][j])continue;
            max_attack[i][j]=max(j,max_attack[i][j+1]);
        }
    }
    for(reg int i=1;i<=m;i++)min_zd[i]=0x3f3f3f3f;
    for(reg int i=m;i>0;i--)
    {\/\/dp
        for(reg int j=1;j<=n;j++)
        {
            if(!attack[j][i])continue;
            min_zd[i]=min(min_zd[i],min_zd[max_attack[j][i]+1]+1);
        }\/\/当前炸起最远能炸到max_attack[j][i]，加上1就到了下一个炸弹所对应的武器区间。
        \/\/所以min_zd[max_attack[j][i]+1]就是下一个炸弹对应的武器区间炸起所需要的最少炸弹。
        \/\/min_zd[max_attack[j][i]+1]还要加上1是因为要考虑到min_zd[max_attack[j][i]+1]是后面的武器区间，
        \/\/还需要算上当前炸弹。
    }
    ans=n;
}
int main()
{
    indata();
    init();
    dfs(1,0);
    printf("%d",ans);
    return 0;
}