csu 1536 Bit String Reordering(模拟 bfs+状态压缩)

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1536

题意： 输入n个只为 0或1 的数 形成一个排列

         再输入m个数 每个数代表 目标排列

       （样例

     1 0 0 1 0 1
     1 3 2

     目标排列有可能为
     1 0 0 0 1 1 或 0 1 1 1 0 0
    ）
    每次只能移动相邻的数

         问最少几步达到

思路：1 纯模拟 

           对目标串分类讨论

          如果起始串和目标串上对应位置数字不一样

          swap(b[j],b[i]);

          ans+=j-i;

       2 bfs+状态压缩

         将起始串和两种可能的目标串状压 

         并bfs相邻状态 记录步数

         达到目标串状态时 输出结果      

模拟:

#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=20;
int a[MAXN],b[MAXN],num[MAXN],temp[MAXN],ans;
void swap(int &a,int &b)
{int temp;temp=a;a=b;b=temp;
}
int min(int a,int b)
{if(a>b) return b;else return a;
}
int main()
{int n,m,num0=0,num1=0,res1=0,res2=0;int minn=0x3f3f3f3f;scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==1) num1++;if(a[i]==0) num0++;}for(int i=1;i<=m;i++){scanf("%d",&temp[i]);if(i%2==1) res1+=temp[i];if(i%2==0) res2+=temp[i];}if(res1==num1){ans=0;memset(b,0,sizeof(b));for(int i=1;i<=n;i++) num[i]=a[i];int flag=1,cnt=1;for(int i=1;i<=m;i++){for(int j=1;j<=temp[i];j++)b[cnt++]=flag;flag=!flag;}for(int i=1;i<=n;i++){if(num[i]==b[i]) continue;else{for(int j=i+1;j<=n;j++){if(b[j]==!b[i]){swap(b[j],b[i]);ans+=j-i;break;}}}}minn=min(ans,minn);}if(res1==num0){ans=0;memset(b,0,sizeof(b));for(int i=1;i<=n;i++) num[i]=a[i];int flag=0,cnt=1;for(int i=1;i<=m;i++){for(int j=1;j<=temp[i];j++)b[cnt++]=flag;flag=!flag;}for(int i=1;i<=n;i++){if(num[i]==b[i]) continue;else{for(int j=i+1;j<=n;j++){if(b[j]==!b[i]){swap(b[j],b[i]);ans+=j-i;break;}}}}minn=min(ans,minn);}printf("%d\n",minn);return 0;
}

bfs+状态压缩

#include 
#include 
#include 
#include 
#include 
#include 
#include 

转载于:https://www.cnblogs.com/sola1994/p/4369259.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！