sicily 1142 迭代深搜

//迭代深搜，继续百度之 //第一次裸深搜，只不过听了同学说最多2*n加了个小剪枝 时间超过10s //第二次广搜+字典树存状态，神勇到达0.8s但是 内存超过32m... //如此如此。。 //最后百度之才知道有种迭代深搜，就是逐层增加搜索次数，这样实现结果从小到大状态搜索 //有点像BFS+DFS。。 //题意，给过最多26个数字，输出最小排序翻转次数，煎饼堆排序 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int n,s[26],num[26]; //low()函数算出当前状态离目标状态最小步数,思想是相隔两个元素差距大于等于2必定有一次翻转 inline int low() { int result = 0; for( int i=0; i < n-1;i++ ) { result += ( s[i] - s[i+1] > 1 || s[i] - s[i+1] < -1 ); } return result; } bool _cmp( int a,int b ) { return num[a]<num[b]; } inline bool value() { for( int i = 0;i < n-1;i++ ) if( s[i] > s[i+1] ) return false; return true; } bool dfs( int k ) { if( k == 0 ) { if( value() ) return true; else return false; } if( low() > k ) return false; for( int i = 2;i <= n;i++ ) { reverse( s,s+i ); if( dfs( k-1 )) return true; reverse( s,s+i ); } return false; } int main() { //freopen( "1.txt","r",stdin ); scanf("%d",&n); for( int i = 0;i < n;i++ ) { s[i] = i; scanf( "%d",num+i ); } sort( s,s+n,_cmp ); int mn = low(); while( true ) if( dfs(mn++) ) break; cout<<mn-1<<endl; return 0; }