hihocoder1233 && 2015亚洲区域赛北京赛区G – Boxes(bfs)

hihocoder1233

【题意】在一个房间里面 有N个 仓库 从左到右是从1 到N

每个仓库里面都有一个箱子， 体积是V（他们体积都是不同的）

你的任务是移动每个仓库中的箱子，让他们最后的顺序是从左到右依次增大

移动的条件是:体积小的才能放在体积大的上面 ,而且只是相邻的仓库之间移动,求最小移动次数。

【分析】很容易看出是搜索题，关键是设计状态，一开始一直去想怎么表示叠加起来的状态，这样状态就太多了，没法做。其实只要表示数字i在哪个位置j的时候的状态，因为每个数字不重复(可以离散)并且只能移动到比他大的箱子上面，这样只要知道每个数位置就能直接表示出叠加起来的状态了(V小的肯定在上面，否则状态不合法)。那么这样有7^7个状态，似乎解决了？

但是不能用记忆化搜索，因为记忆化搜索每次的起点(即输入的状态)不一样，导致每次都必须清空所有保存的值再搜索，而T有6000，必然超时。发现只要数字的数量一样，要到达的终点都一样，那么可以反过来bfs只要7次预处理出每个数量的所有可达到状态即可。这样加上每次转移状态复杂度，总复杂度为7^7*(7*7) = 40353607，可以接受;

而状态只要用8进制压缩和解码，就能让代码变成很短而且很好写。

【AC CODE】183ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100, M = 2097151+10;
int dp[M];//dp[s]表示数i在哪个位置时的状态s下到排完序最少几步

inline int get_hash(int *num, int len)//压缩,1~7,为了避免都为0时不同位数hash值冲突
{
	int ans = 0;
	rep(i,0,len) ans = ans*8+num[i];
	return ans;
}
void get_num(int s, int *num, int &len)//解码
{
	len = 0;
	while(s)
	{
		num[len++] = s%8;
		s /= 8;
	}
	for(int i = 0, j = len-1; i < j; i++ ,j--) swap(num[i],num[j]);
}
int tmp[MAXN];
queue<int> q;
void bfs(int st, int n)
{
	while(!q.empty()) q.pop();
	q.push(st);
	dp[st] = 0;
	int mi[MAXN];//每个位置最上面的数
	while(!q.empty())
	{
		int now = q.front();q.pop();
		int len;
		get_num(now,tmp,len);
		clc(mi,0x3f);
		rep(i,0,len) mi[tmp[i]] = min(mi[tmp[i]],i);
		repe(i,1,n)
		{
			int l = i-1, r = i+1;
			if(mi[i] == INF) continue;
			int buf = tmp[mi[i]];
			if(l >= 1 && mi[i] < mi[l])
			{
				tmp[mi[i]] = l;
				int v = get_hash(tmp,len);
				if(-1 == dp[v])
				{
					dp[v] = dp[now]+1;
					q.push(v);
				}
				tmp[mi[i]] = buf;
			}
			if(r <= n && mi[i] < mi[r])
			{
				tmp[mi[i]] = r;
				int v = get_hash(tmp,len);
				if(-1 == dp[v])
				{
					dp[v] = dp[now]+1;
					q.push(v);
				}
				tmp[mi[i]] = buf;
			}
		}
	}
}

int a[MAXN];
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int buf[MAXN]={1,2,3,4,5,6,7};
	clc(dp,-1);
	repe(i,1,7) bfs(get_hash(buf,i),i);
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n;
		scanf("%d", &n);
		rep(i,0,n) scanf("%d", &a[i]),tmp[i] = a[i];
		sort(tmp,tmp+n);
		rep(i,0,n) buf[lower_bound(tmp,tmp+n,a[i])-tmp] = i+1;
		printf("%d\n",dp[get_hash(buf,n)]);
	}
	return 0;
}