题目传送门(BZOJ)
>原文链接<

题解 :

网上大片大片的 IDA* 然鹅并不需要那个。

手推最坏情况 9 8 7 6 5 4 3 2 1 后你会发现答案不超过5。

所以我们可以折半搜索,从初始状态搜 3 步,再从排好序的状态搜两步。

然后你发现这样做需要20多秒。

所以我尝试着把状态哈希,减少重复状态带来的影响。效果显而易见,我们压到了3秒。

然鹅我们那场考试时限是 1s, 所以我还是只得了部分分。毕竟复杂度还是不对。

但是你发现,如果从左边搜两步,右边搜两步之后,没有交集的话,答案必然是5,

所以我们初始状态只搜两步。

这…. 神仙复杂度。

注意 :初始输入可能是有序的,如果不把这个状态放到map里,可以被卡掉的。

代码 :

#include <tr1/unordered_map>#include <map>#include <ctime>#include <queue>#include <cstdio>#include <cstring>#include <iostream>using namespace std;using namespace std::tr1;unordered_map<int, int>f, g;map<int, int>hadans;queue<pair<int, int> >q;int n, a[10];inline int merge(int* tmp) { int ret = 0; for(int i = n; i >= 1; i -- )ret = (ret<<3)+(ret<<1) + tmp[i]; return ret;}inline void split(int x, int* a) { for(int i = 1; i <= n; i ++, x/=10) a[i] = x%10;}int ans = 0;void Get_Front() { int x = 0; for(int i = n; i >= 1; i -- )x = (x<<3)+(x<<1) + a[i]; pair<int, int>pa; pa.first = x, pa.second = 0; q.push(pa); while(!q.empty()) { int u = q.front().first, stp = q.front().second; q.pop(); stp++; if(stp >= 3) break; split(u, a); for(int l = 1; l <= n; l ++ ) for(int r = l; r <= n; r ++ ) for(int k = 1; k+r-l <= n; k ++ ) { int tmp[10]; int p1 = k, p2 = l; while(p2 <= r) tmp[p1++] = a[p2++]; p1 = 1, p2 = 1; while(p1 <= n) { if(p1 == k) p1 = k+r-l+1; if(p2 == l) p2 = r+1; tmp[p1++] = a[p2++]; } int now = merge(tmp); if(!f[now]) { f[now] = stp; pa.first = now, pa.second = stp; q.push(pa); } } }}void Find_Ans() { while(!q.empty()) q.pop(); int x = merge(a); if(f[x]) ans = min(ans, f[x]); q.push(make_pair(x, 0)); while(!q.empty()) { int u = q.front().first, stp = q.front().second; q.pop(); stp++; if(stp >= 3) break; split(u, a); for(int l = 1; l <= n; l ++ ) for(int r = l; r <= n; r ++ ) for(int k = 1; k+r-l <= n; k ++ ) { int tmp[10]; int p1 = k, p2 = l; while(p2 <= r) tmp[p1++] = a[p2++]; p1 = 1, p2 = 1; while(p1 <= n) { if(p1 == k) p1 = k+r-l+1; if(p2 == l) p2 = r+1; tmp[p1++] = a[p2++]; } int now = merge(tmp); if(f[now]) ans = min(ans, f[now] + stp); if(!g[now]) { g[now] = 1; q.push(make_pair(now, stp)); } } }}int main() { while(scanf("%d", &n), n != 0) { f.clear(); g.clear(); ans = 5; while(!q.empty()) q.pop(); for(int i = 1; i <= n; i ++ ) a[i] = i; int y = merge(a); for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); int x = merge(a); if(x==y) { puts("0"); continue; } if(hadans[x]) { printf("%d\n", hadans[x]); continue; } Get_Front(); for(int i = 1; i <= n; i ++ ) a[i] = i; Find_Ans(); printf("%d\n", hadans[x]=ans); }}