作者：瓜瓜哥哥 | 来源：互联网 | 2023-05-18 19:09
DescriptionB国在耗资百亿元之后终于研究出了新式武器——连环阵（ZenithProtectedLinkedHybridZone）。传说中，连环阵是一种永不停滞
Description
B国在耗资百亿元之后终于研究出了新式武器——连环阵（Zenith Protected Linked Hybrid Zone）。传说中，连环阵是一种永不停滞的自发性智能武器。但经过A国间谍的侦察发现，连环阵其实是由M个编号为1，2，…，M的独立武器组成的。最初，1号武器发挥着攻击作用，其他武器都处在无敌自卫状态。以后，一旦第i（1<=i
Input
第一行包含三个整数：M、n和k（1<=M, n<=100，1<=k<=1000），分别表示B国连环阵由M个武器组成，A国有n个炸弹可以使用，炸弹攻击范围为k。以下M行，每行由一对整数xi，yi（0<=xi，yi<=10000）组成，表示第i（1<=i<=M）号武器的平面坐标。再接下来n行，每行由一对整数ui，vi(0<=ui，vi<=10000)组成，表示第i（1<=i<=n）号炸弹的平面坐标。输入数据保证随机、无误、并且必然有解。
Output
一行包含一个整数x，表示实际使用的炸弹数.
Sample Input
Sample Input 1
4 3 6
0 6
6 6
6 0
0 0
1 5
0 3
1 1
Sample Input 2
10 10 45
41 67
34 0
69 24
78 58
62 64
5 45
81 27
61 91
95 42
27 36
91 4
2 53
92 82
21 16
18 95
47 26
71 38
69 12
67 99
35 94
Sample Output
Sample Output 1
2
Sample Output 2
5
HINT
输出数据为NOI原数据
输出数据由楼教主代码制作
原题有spj 此题去掉spj 只输出最优解
HINT
NOI2003 Day2 T3 感谢sxb_201上传
正解：搜索+$dp$+二分图最大匹配。
丧心病狂的$zjo$竟然把这题出成考试题。。我敢说这是我见过的最玄学的搜索题。。
首先，我们发现每个炸弹肯定炸一段连续的区间。那么有一个很直观的暴力的思路，那就是枚举区间。对于每个区间，能够完全覆盖的炸弹向它连边，跑一遍二分图最大匹配就行了。
这样显然是过不了的，所以我们要剪枝。我们假设每个炸弹可以重复使用，那么我们算出当前武器开始的所有武器最少还需几个炸弹才能消灭。
这个用$dp$来预处理。设$can[p][i][j]$表示$p$号炸弹，是否能够炸$[i,j]$这个区间。那么设$dis[i]$表示炸$[i,m]$需要的最少炸弹，易知$dis[i]=min(dis[j]+1)$，$i
最优性剪枝：$now+dis[i]>=ans$则剪枝，$now$为当前炸弹数。
可行性剪枝：我们可以每次直接在原图的基础上进行增广，如果当前点不能进行增广，就不用再往下搜索了。
然而这些剪枝还是不足以通过全部数据，我们不妨从可行性剪枝上入手。
我们可以尝试求出当前区间右端点的最大值$maxl$，那么显然，$maxl$及其之前的端点都是可行的。
我们发现这样可以很大程度地优化时间。首先，我们可以从$maxl$到$l$依次枚举右端点，减少搜索量；其次，我们可以只进行一次增广，因为$can[p][i][j]>=can[p][i][j+1]$，那么右端点为$maxl$时连的边，在右端点减小时同样也会出现，并不会影响答案。
如何求出$maxl$？首先我们要求出辅助数组$maxt[p][l]$，表示炸弹$p$从$l$开始能炸到的最远的点的编号，这个很容易预处理出来，就不再赘述。
注意到匈牙利算法的过程，一个炸弹能够使用有两种情况。首先是这个炸弹没有出现在匹配边上；其次是这个炸弹虽然出现在匹配边上，但是它能够通过增广以后和当前区间匹配。那么我们就可以使用$bfs$来解决这个问题，求出所有能够使用的炸弹(具体操作看代码吧。。)，然后不断地取$maxt[p][l]$的最大值，就能求出$maxl$了。
这就是本题的两个重要剪枝，加上这两个剪枝以后极限数据也可以瞬间求解了。
1 //It is made by wfj_2048~
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
42 for (RG int j=i+1;j<=m;++j){
43 can[p][i][j]=can[p][i][j-1]&g[p][j];
44 if (can[p][i][j]) maxt[p][i]=j;
45 }
46 }
47 for (RG int i=m;i;--i){
48 dis[i]=inf;
49 for (RG int j=i;j<=m;++j)
50 for (RG int p=1;p<=n;++p)
51 if (can[p][i][j]) dis[i]=min(dis[i],dis[j+1]+1);
52 }
53 return;
54 }
55
56 il int hungry(RG int x){
57 for (RG int v=1;v<=n;++v){
58 if (!g[x][v] || vis[v]==cnt) continue; vis[v]=cnt;
59 if (!lk[v] || hungry(lk[v])){ mt[x]=v,lk[v]=x; return 1; }
60 }
61 return 0;
62 }
63
64 il void dfs(RG int l,RG int id){
65 if (l>m){ ans=id-1; return; } if (id-1+dis[l]>=ans) return;
66 ++cnt; RG int LK[N],MT[N],h=0,t=0,maxl=l-1;
67 for (RG int i=1;i<=n;++i) if (!lk[i]) vis[i]=cnt,q[++t]=i;
68 while (h<t){
69 RG int x=q[++h]; maxl=max(maxl,maxt[x][l]);
70 for (RG int i=1;ii)
71 if (g[i][x] && vis[mt[i]]!=cnt) vis[mt[i]]=cnt,q[++t]=
mt[i];
72 }
73 memcpy(LK,lk,
sizeof(LK)),memcpy(MT,mt,
sizeof(MT));
74 for (RG
int i=
1;i<=n;++i) g[id][i]=can[i][l][maxl]; ++
cnt,hungry(id);
75 for (RG
int r=maxl;r>=l;--
r){
76 for (RG
int i=
1;i<=n;++i) g[id][i]=can[i][l][r]; dfs(r+
1,id+
1);
77 }
78 memcpy(lk,LK,
sizeof(lk)),memcpy(mt,MT,
sizeof(mt));
return;
79 }
80 81 il
void work(){
82 m=gi(),n=gi(),k=gi(),pre(),ans=
n;
83 dfs(
1,
1),printf(
"%d\n",ans);
return;
84 }
85 86 int main(){
87 File(
"boom");
88 work();
89 return 0;
90 }
![一文了解Python collections模块中的deque用法[python头条资讯]](https://img1.php1.cn/3cd4a/24ed6/5a0/5b2593d9bb299e5e.jpeg)
京公网安备 11010802041100号