移动一块连续的区间使得数列递增。问最少次数。

直接IDA*暴搜，不过我没有想到A*函数，所以就随手写了个连续递增块数作为估价函数，WA了，然后除以2，还是WA，除以3，WA，除以4.。。过了= =

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; #define stop system("pause") int n,a[20],lim; void print(int *a){for(int i=1;i<=n;i++) printf("%d ",a[i]);puts("");} int h(int *s) { int cnt=0; for(int i=1;i
        
         =from-1&&to<=ed) return false; int next[20],tmp[20]; for(int i=0;i<=n;i++) tmp[i]=s[i],next[i]=i+1; next[from-1]=ed+1; next[to]=from; next[ed]=to+1; for(int i=next[0],cnt=1;cnt<=n;i=next[i],cnt++) { s[cnt]=tmp[i]; } return true; } bool over(int *a) { for(int i=1;i<=n;i++) if(a[i]!=i) return false; return true; } bool dfs(int dep,int *s) { if(over(s)) return true; if(dep>=lim) return false; if(dep+h(s)>=lim) return false; for(int from=1;from<=n;from++) { for(int ed=from;ed<=n;ed++) { for(int to=0;to<=n;to++) { int tmp[15]; memcpy(tmp,s,sizeof(int)*(n+1)); if(change(from,ed,to,tmp)==0) continue; if(dfs(dep+1,tmp)) return true; } } } return false; } int main() { int ca=1; while(~scanf("%d",&n)) { if(n==0) break; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(lim=h(a);!dfs(0,a);lim++) ; printf("Case %d: %d\n",ca++,lim); } return 0; } /* 9 9 8 7 6 5 4 3 2 1 */