呵呵哒

c++

#include <cstdio>

#include <cstring>

#include <cstdlib>

#define l 110

int x1[l],y1[l],x2[l],y2[l],m,n,k,MAXT[l][l],ans=1000000000,a[l],b[l],vis[l],dl[l],head,tail,perfect[l];

bool reach[l][l],can[l][l][l],g[l][l];

void input_data()//读入数据

{

scanf("%d%d%d",&m,&n,&k);

for (int i=1;i<=m;i++)

scanf("%d%d",&x1[i],&y1[i]);

for (int i=1;i<=n;i++)

scanf("%d%d",&x2[i],&y2[i]);

for (int i=1;i<=m;i++)

for (int j=1;j<=n;j++)

reach[i][j]=((x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j]))<=(k*k);//reach[i][j]表示i号武器能否被j号炸弹炸到。

}

void pre()

{

for (int i=1;i<=m;i++)

{

for (int j=1;j<=n;j++)

can[i][i][j]=reach[i][j];//can[i][j][k]表示k号炸弹是否能炸毁i-j号武器

for (int j=i+1;j<=m;j++)

for (int d=1;d<=n;d++)

can[i][j][d]=can[i][j-1][d] && reach[j][d];//更新

for (int j=1;j<=n;j++)

{

MAXT[i][j]=i-1;//MAXT[i][j]表示j号炸弹从i号武器开始能够炸到的最大编号

for (int d=i;d<=m;d++)

if (can[i][d][j]) MAXT[i][j]=d;//利用can数组来更新MAXT数组

}

}

perfect[m+1]=0;//perfect[i]表示i-m号武器最少需要多少个炸弹才能炸掉(可以重复使用炸弹);

for (int i=m;i>=1;i--)

{

int t=i-1;

for (int j=1;j<=n;j++)

if (MAXT[i][j]>t) t=MAXT[i][j];//找到这个炸弹的最大使用限度。

perfect[i]=perfect[t+1]+1;//从t+1转移到当前状态。

}

}

bool xiongyali(int x)//匈牙利算法

{

for (int i=1;i<=n;i++)

if (g[x][i] && !vis[i])

{

vis[i]=true;

if (b[i]==0 || xiongyali(b[i]))

{

a[x]=i;

b[i]=x;

return true;

}

}

return false;

}

void search_ans(int used,int now)//used表示已经使用过的炸弹数，now表示now之前的武器都已经被炸毁

{

if (used+perfect[now]>=ans) return;//如果当前已经使用过的炸弹加上now---m的最少使用炸弹数>=ans则退出.

if (now==m+1)//如果已经炸掉了所有的武器则更新答案。

{

ans=used;

return;

}

int tempa[l],tempb[l],maxl=now-1;//开始划分这一段的区间。

memset(vis,false,sizeof(vis));

head=tail=0;

for (int i=1;i<=n;i++)

if (b[i]==0) //没有被使用过 则入队。

{

vis[i]=true;

dl[++tail]=i;

}

while (head<tail)
{
int k=dl[++head];//取出在队中的炸弹
if (maxl<MAXT[now][k])//如果这个炸弹从now开始能够炸到更大的编号则更新
maxl=MAXT[now][k];
for (int i=1;i<used;i++)//回过头来查看原先使用过的炸弹，看看能否用匈牙利算法的思路改变原来的匹配，获得更大的值。
if (g[i][k] && !vis[a[i]])
{
vis[a[i]]=true;
dl[++tail]=a[i];
}
}
if (maxl==now-1) return;//如果已经不能完成匹配了就结束。
used++;
memcpy(g[used],can[now][maxl],sizeof(can[now][maxl]));//左边是区间，右边是炸弹，表示可以使用这些炸弹炸掉这段区间，因此连边。
memcpy(tempa,a,sizeof(a));//用于回溯
memcpy(tempb,b,sizeof(b));
memset(vis,false,sizeof(vis));//匈牙利算法的判重
xiongyali(used);//给used这个点匹配。
for (int i=maxl;i>=now;i--)//从大到小枚举区间。增强perfect数组的作用。

{

memcpy(g[used],can[now][i],sizeof(can[now][i]));

search_ans(used,i+1);

}

memcpy(a,tempa,sizeof(a));

memcpy(b,tempb,sizeof(b));

}

void output_ans()

{

printf("%d\n",ans);

}

int main()

{

input_data();

pre();

search_ans(0,1);

output_ans();

return 0;

}

希望能对你有帮助，谢谢

希望你能通过

你可以试试其他的算法，加油

我也不知道