首页 > 代码库 > UVA 11212 IDA*
UVA 11212 IDA*
移动一块连续的区间使得数列递增。问最少次数。
直接IDA*暴搜,只是我没有想到A*函数,所以就随手写了个连续递增块数作为估价函数,WA了,然后除以2,还是WA,除以3,WA,除以4.。。过了= =
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<list> #include<algorithm> 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<n;i++) if(s[i]+1!=s[i+1]) cnt++; if(s[n]!=n) cnt++; return cnt/4; } bool change(int from,int ed,int to,int *s) { if(to>=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 */
貌似正解应该是 dep*3+h()>lim*3
UVA 11212 IDA*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。