自动搬运

查看原文

来自洛谷，原作者为

	tc291311 **

搬运于2025-08-24 21:26:05，当前版本为作者最后更新于2025-07-22 11:37:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[NOI2003] 智破连环阵

原题链接

一道很好的思维优化题！

正片开始！

题意概括

在坐标轴第一象限中有 $M$ 个武器，$N$ 个炸弹，每个武器按顺序开启可被摧毁状态，以下简称 $D$ 状态，若一个武器在炸弹的爆炸范围内，则这个武器将被摧毁，紧接着下一个武器将会开启 $D$ 状态。
求安排炸弹的爆炸顺序，使得摧毁全部武器使用的炸弹最小。

是不是看起来还不算很难？爆搜不就过了？哈哈，爆炸了。

正解

一个炸弹摧毁的一定是连续的一段区间，所以整个武器序列可分为几段，每段被都某个炸弹摧毁。
当前 DFS 到的区间右端点为 $r$，划分了 $cnt$ 个区间。预处理出 $Maxt_{i,j}$ 表示 $i$ 炸弹从 $j$ 武器开始可以炸到的最右端点。
于是我们可以轻松的写出关系式：

千万注意不要写错了，不然就会调 1 个月，别问我怎么知道的，我也不知道。

但是我们现在想要知道的是炸掉武器 $A_{i,m}$ 需要炸弹数的下界用来剪枝，于是便能推出以下结论：

将上述结果设为 $Minc_i$ 且不考虑炸弹数量的限制，既有无数个炸弹。很容易的就推出了转移方程：

有点晕是不是，来解释一下刚刚的柿子。

它的含义是：对于每一个炸弹 $j$，如果它从第 $i$ 个武器开始炸起，那么它能炸到的最右端点是 $Maxt_{j,i}$。因此，从 $i$ 开始炸起，至少需要一个炸弹（即 +1），然后从 $Maxt_{j,i+1}$ 开始继续炸起，所需的炸弹数量为 $Minc_{Maxt_{j,i}+1}$。我们需要对所有可能的炸弹 $j$ 进行遍历，取其中的最小值。大概懂了吧？

于是可以对武器序列的分界点进行搜索，若一个炸弹可以炸掉一个区间，则这个炸弹与那个区间连边，最终得到一个标准的二分图。于是使用匈牙利在搜索中剪枝即可。

匈牙利算法在文末有解释。

此时的 $a$ 炸弹能与 $b$ 区间连边需要满足的条件为：

• 可以完全的覆盖整个区间，也能说 $Maxt_{a,l_b}\ge r_b$。

代码实现

注意！！！

• 匈牙利可以在深搜过程中进行。
• 该倒序循环的不要忘记倒序循环。
• 全局数组的清空。
• 一开始的答案要赋值为 $n$，不能赋值成极大值，这样会导致答案得出前剪枝会失效。

#include<bits/stdc++.h>
#define reg register

const int maxn = 105;

int M;
int N;
int K;
int Ans;
int mark[maxn];
int Min_cost[maxn];
int Max_t[maxn][maxn];

bool Used[maxn];
bool like[maxn][maxn];

struct Node{ int x, y; } A[maxn], B[maxn];

bool Pd(Node zd, Node wq){
        int t1 = zd.x-wq.x, t2 = zd.y-wq.y;
        return t1*t1 + t2*t2 <= K*K;
}

bool Find(int x){
        for(reg int i = 1; i <= N; i ++)
                if(like[i][x] && !Used[i]){
                        Used[i] = 1;
                        if(!mark[i] || Find(mark[i])){ mark[i] = x; return 1; }
                }
        return 0;
}

void DFS(int k, int cnt){
        if(cnt + Min_cost[k] >= Ans) return ;
        if(k == M+1){ Ans = std::min(Ans, cnt); return ; }
        int Tmp_1[maxn];
        for(reg int i = k; i <= M; i ++){
//                memcpy(Tmp_1, mark, sizeof Tmp_1);
                for(reg int j = 1; j <= N; j ++){
                        Tmp_1[j] = mark[j];
                        if(Max_t[j][k] >= i) like[j][cnt+1] = 1; 
                }
                
                memset(Used, 0, sizeof Used);
                if(Find(cnt+1)) DFS(i+1, cnt+1);

                for(reg int j = 1; j <= N; j ++){
                	mark[j] = Tmp_1[j];
                        if(Max_t[j][k] >= i) like[j][cnt+1] = 0;
                }
//                memcpy(mark, Tmp_1, sizeof mark);
        }
}

int main(){
        scanf("%d%d%d", &M, &N, &K);
        for(reg int i = 1; i <= M; i ++) scanf("%d%d", &A[i].x, &A[i].y);
        for(reg int i = 1; i <= N; i ++) scanf("%d%d", &B[i].x, &B[i].y);
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = M; j >= 1; j --)
                        if(Pd(B[i], A[j])) Max_t[i][j] = std::max(Max_t[i][j+1], j);
        memset(Min_cost, 0x3f, sizeof Min_cost);
        Min_cost[M+1] = 0;
        for(reg int i = M; i >= 1; i --)
                for(reg int j = 1; j <= N; j ++)
                        if(Pd(B[j], A[i]))
                                Min_cost[i] = std::min(Min_cost[i], Min_cost[Max_t[j][i] + 1] + 1);
        Ans = N;
        DFS(1, 0);
        printf("%d\n", Ans);
        return 0;
}

匈牙利算法简单介绍

匈牙利算法是一种用于解决二分图最大匹配问题的算法，其核心思想是通过寻找增广路径来逐步增加匹配的边数。它通常通过深搜实现，时间复杂度为 $O(nm)$。算法的基本步骤包括：初始化匹配状态，遍历每个顶点，尝试匹配未被访问的顶点，如果匹配成功则更新匹配状态，并递归地寻找下一个顶点的匹配。最终，算法返回最大匹配的数量。

还是不懂的可以参考这篇文章。

完结撒花！！！❀