【题意】在一个房间里面 有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; }