（以下在描述复杂度时，认为$n$和$m$相同，因此一律使用$n$）
称第$i$个炸弹能匹配非空区间$[l,r]$，当且仅当$l$到$r$内所有武器都在$i$攻击范围内，且$r=m$或第$r+1$个武器不在$i$攻击范围内
（更通俗的表示即在第$l$个武器启动时，使用第$i$个炸弹恰好会攻击到第$r$个武器）
关于这个区间的匹配，显然可以在$o(n^{2})$的时间内预处理
下面，将$n$个武器划分为若干个区间，分别表示每一个炸弹所破坏的武器（恰好），爆搜来确定区间划分后，只需判定其是否合法，并用区间数对答案取$min$即可
关于判定，将第$i$个炸弹向划分出的区间中能匹配的区间连边，判定最大匹配是否等于区间数即可
暴搜复杂度为$o(n^{2}2^{n})$（即每一个位置是否划分，以及二分图匹配），下面来考虑剪枝——
剪枝1：求出$[i,n]$这些武器，在允许重复利用炸弹的情况下的最少次数$g_{i}$
若当前划分出$now$个区间，最后一个区间右端点为$r$，最小答案为$ans$，那么若$now+g_{r+1}ge ans$显然不需要搜索下去，直接返回即可
关于$g_{i}$的计算，即$g_{i}=min_{炸弹j能匹配区间[i,k]}g_{k+1}+1$（初始$g_{m+1}=0$），复杂度为$o(n^{3})$
剪枝2：在搜索过程中，每一次划分出一个区间后，即在最终的二分图中新增一个点，根据二分图的过程，直接对其再求一次匹配，当某一次无法匹配直接退出即可
剪枝3：从后往前枚举右端点，在综合剪枝1和剪枝2的基础上，此优化也有一定的用处
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 struct point{ 5 int x,y; 6 }a[N],b[N]; 7 vector<int>v[N<<1]; 8 int n,m,k,ans,g[N],Vis[N][N][N],mm[N][N<<1],vis[N<<1],match[N<<1]; 9 int sqr(int k){ 10 return k*k; 11 } 12 bool check(point x,point y){ 13 return sqr(x.x-y.x)+sqr(x.y-y.y)<=sqr(k); 14 } 15 bool dfs(int k){ 16 if (vis[k])return 0; 17 vis[k]=1; 18 for(int i=0;i<v[k].size();i++) 19 if ((!match[v[k][i]])||(dfs(match[v[k][i]]))){ 20 match[k]=v[k][i]; 21 match[v[k][i]]=k; 22 return 1; 23 } 24 return 0; 25 } 26 void dfs(int k,int s){ 27 if (s+g[k]>=ans)return; 28 if (k>m){ 29 ans=s; 30 return; 31 } 32 memcpy(mm[s],match,sizeof(mm[s])); 33 for(int i=m;i>=k;i--){ 34 for(int j=1;j<=n;j++) 35 if (Vis[j][k][i])v[n+s+1].push_back(j); 36 memset(vis,0,sizeof(vis)); 37 if (dfs(n+s+1)){ 38 dfs(i+1,s+1); 39 memcpy(match,mm[s],sizeof(mm[s])); 40 } 41 for(int j=1;j<=n;j++) 42 if (Vis[j][k][i])v[n+s+1].pop_back(); 43 } 44 } 45 int main(){ 46 scanf("%d%d%d",&m,&n,&k); 47 for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y); 48 for(int i=1;i<=n;i++){ 49 scanf("%d%d",&b[i].x,&b[i].y); 50 for(int j=1;j<=m;j++){ 51 if (!check(b[i],a[j]))continue; 52 for(int k=j;k<=m+1;k++) 53 if ((k>m)||(!check(b[i],a[k]))){ 54 Vis[i][j][k-1]=1; 55 break; 56 } 57 } 58 } 59 g[m+1]=0; 60 for(int i=m;i;i--){ 61 g[i]=n; 62 for(int j=1;j<=n;j++) 63 for(int k=i;k<=m;k++) 64 if (Vis[j][i][k])g[i]=min(g[i],g[k+1]+1); 65 } 66 ans=n; 67 dfs(1,0); 68 printf("%d",ans); 69 }