[HAOI2008]移动玩具 状压

本文主要是介绍[HAOI2008]移动玩具 状压，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

发现自己只会打状压了。 233333

不需要考虑是否会被挡，所以直接dp

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int tot1,tot2,a[5][5],b[5][5];
int x1[20],x2[20],y11[20],y2[20];
char ch;
int dis[20][20],f[20][1<<10],bit[15],n;
int main()
{bit[0]=1; for(int i=1;i<=10;i++) bit[i]=bit[i-1]<<1;for(int i=1;i<=4;i++)for(int j=1;j<=4;j++){ch=getchar();while(ch<'0'||ch>'1')ch=getchar();a[i][j]=ch-'0';}for(int i=1;i<=4;i++)for(int j=1;j<=4;j++){ch=getchar();while(ch<'0'||ch>'1')ch=getchar();b[i][j]=ch-'0';}for(int i=1;i<=4;i++)for(int j=1;j<=4;j++){if(a[i][j]==b[i][j]) continue;if(a[i][j]==1) x1[++tot1]=i,y11[tot1]=j;if(b[i][j]==1) x2[++tot2]=i,y2[tot2]=j;}for(int i=1;i<=tot1;i++)for(int j=1;j<=tot2;j++)dis[i][j]=abs(x1[i]-x2[j])+abs(y11[i]-y2[j]);n=tot1; memset(f,0x3f,sizeof f);f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<bit[n];j++){if(f[i-1][j]==1061109567) continue;for(int k=1;k<=n;k++){if((j|bit[k-1])==j) continue;if(f[i-1][j]+dis[i][k]<f[i][j|bit[k-1]])f[i][j|bit[k-1]]=f[i-1][j]+dis[i][k];}}}printf("%d\n",f[n][bit[n]-1]);return 0;
}

这篇关于[HAOI2008]移动玩具 状压的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---