P1526 [NOI2003] 智破连环阵题解

· · 个人记录

难度：\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;
}