首页 > 代码库 > UVa11212，Editing a Book

UVa11212，Editing a Book

2024-07-15 02:58:01   218人阅读

正如书上所说，本题需要用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;    }}
View Code

 


联系
我们