首页 > 代码库 > UVa11212,Editing a Book
UVa11212,Editing a Book
正如书上所说,本题需要用IDA*算法求解
启发函数是3d+h>3maxd(d为当前操作步骤数,h为当前逆序对数,maxd为当前枚举的最大步骤数)
可见迭代递归的核心思想是枚举ans去dfs是否可行,相反常规搜索是dfs去需找ans。
一开始卡在状态图的转移与回溯上,参考(http://blog.csdn.net/sssogs/article/details/8836606)大神的代码后得到启发,可以将图或是表直接写成结构体或是类跟着递归走(当然,图或是表不能很大,比较大的话应该还是用回溯比较好吧)
#include <iostream>#include <cstring>#include <cstdio>#include <string>#include <algorithm>#define maxn 20using namespace std;int maxd,cnt;class MyClass{ public: int map[maxn]; int h,n; void move(int s,int e,int k){ int t[maxn]; for (int i=0;i<k;i++){ t[i]=map[i]; } for (int i=s;i<=e;i++){ t[k+i-s]=map[i]; } int top=k+e-s; for (int i=k;i<n;i++){ if (i<s||i>e) t[++top]=map[i]; } memcpy(map,t,sizeof(t)); } void move2(int s,int e,int k){ int t[maxn],i,j; for (i=0; i<s; i++) { t[i]=map[i]; } for (j=e+1; j<k; j++,i++) { t[i]=map[j]; } for (j=s; j<=e; j++,i++) { t[i]=map[j]; } for (j=k; j<n; j++,i++) { t[i]=map[j]; } memcpy(map,t,sizeof(t)); } int getH(){ h=0; for (int i=0;i<n-1;i++) if (map[i]+1!=map[i+1]) h++; if (map[n-1]!=n) h++;//经过测试,这一句减掉了60%的搜索量.......之前一直TLE,天呢,又是一下午 return h; } bool init(){ cin>>n; if (n==0) return false; for (int i=0;i<n;i++){ cin>>map[i]; } return true; }};int IDAdfs(int d,MyClass c){ c.getH(); MyClass tc; cnt++; if (c.h==0) return 1; //if (d==maxd&&c.h>0) return 0; if (3*d+c.h>3*maxd) return 0; for (int i=0;i<c.n;i++) for (int j=i;j<c.n;j++){ for (int k=0;k<i;k++){ tc=c; tc.move(i,j,k); if (IDAdfs(d+1,tc)) return 1; } for (int k=j+2; k<c.n; k++) { tc=c; tc.move(i,j,k); if (IDAdfs(d+1,tc) == true) return true; } } return 0;}int main(){ MyClass b; int prob; prob=1; while (b.init() == true) { cnt=0; for (maxd=0; ; maxd++) { if (IDAdfs(0,b) == true) break; } printf("Case %d: %d\n",prob,maxd); prob++; //cout<<cnt<<endl; }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。