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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
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
",minn);
return 0;
}
bfs+状态压缩
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#define N 1000005
#define lson o<<1, l, m
#define rson o<<1|1, m + 1, r
#define mod 1000000007
using namespace std;
typedef long long LL;
int n,m;
int vis[100050];
int a[20],b[20],c[20];
int ans[2];
int st;
int bfs()
{
int pre[100005];
int begin = 0,end = 1;
pre[0] = st;
int t[100006];
t[0] = 0;
while(begin < end)
{
int w = pre[begin];
if(w == ans[0] || w == ans[1])
{
return t[begin];
}
int i;
int g = 1;
int now;
for(i = 0; i < n - 1; i++)
{
if(((w >> i) & 1) != ((w >>(i + 1)) & 1))
{
if(((w >> i) & 1) == 1)
{
now = w + g;
}
else
{
now = w - g;
}
if(vis[now] == 0)
{
vis[now] = 1;
pre[end] = now;
t[end++] = t[begin] + 1;
}
}
g *= 2;
}
begin++;
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
int i,j;
st = 0;
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
int g = 1;
for(i = n - 1; i >= 0; i--)
{
st += a[i] * g;
g *= 2;
}
for(i = 0; i < m; i++)
{
scanf("%d",&b[i]);
}
g = 0;j = 0;
for(i = 0; i < m; i++)
{
for(int k = 0; k < b[i]; k++)
{
c[j++] = g;
}
g ^= 1;
}
ans[0] = ans[1] = 0;
g = 1;
for(i = n - 1; i >= 0; i--)
{
ans[0] += c[i] * g;
g *= 2;
}
g = 1;j = 0;
for(i = 0; i < m; i++)
{
for(int k = 0; k < b[i]; k++)
{
c[j++] = g;
}
g ^= 1;
}
g = 1;
for(i = n - 1; i >= 0; i--)
{
ans[1] += c[i] * g;
g *= 2;
}
memset(vis,0,sizeof(vis));
printf("%d
",bfs());
}
return 0;
}