1.迭代加深

顾名思义说明迭代的层数逐渐加深，这样做法有点像bfs的做法层层突出，符合的题型是答案在层数较低的那一层里

加成序列

题目https://www.acwing.com/problem/content/description/172/

#includeusing namespace std;const int N=110;int n;int path[N];bool dfs(int u,int depth)//第一个是元素个数，第二个是当前的深度{if(u>depth) returnfalse;//假如元素大于深度，说明不可能了if(path[u-1]==n) return true;//假如元素个数达到深度，且最后一个是n，则说明符合条件bool st[N]={0};//用来标记那个数已经枚举过for(int i=u-1;i>=0;i--)//枚举前u个数，两两可以相加，相当于组合数for(int j=i;j>=0;j--){ int s=path[i]+path[j];//获取这两个数的值 if(st[s]||s>n||s>n,n) { int depth=1;//枚举深度，大概知道答案在比较近的一层，所以不枚举宽度 while(!dfs(1,depth)) depth++;//假如这个深度不符合，则加1 for(int i=0;i<depth;i++) cout<<path[i]<<' ';//输出答案 puts(""); } return 0;}

2.双向dfs

顾名思义就是分两段dfs，搜索前半段与后半段

送礼物

第一种使用了unique函数判重可能会超时

#includeusing namespace std;typedef long long ll;const int N=110;int n,k;int cnt=1;ll w[N],m,weight[1<m) return;//假如已经大于了，则直接返回if(u==k)//假如搜到了最后一个{weight[cnt++]=s;//把这个值放进数组里来return;//这里不能少}dfs1(u+1,s);//假如不选这个数if(s+w[u]m) return;//假如已经大于了，则直接返回 if(u==n)//假如搜到了最后一个 { //下面二分有左边界，因为找刚好小于m的最大数int l=0,r=cnt-1;while(l>1;if(weight[mid]+s<=m) l=mid;else r=mid-1;} ans=max(ans,s+weight[l]);//更新一下答案 return;//这里不能少 }dfs2(u+1,s);//假如不选这个数if(s+w[u]>m>>n;for(int i=0;i>w[i];//从大到小排序sort(w,w+n);reverse(w,w+n);k=n/2+1;//对半分开搜索dfs1(0,0);//搜索前半段，打表出来存进数组里头//去重sort(weight,weight+cnt);cnt=unique(weight,weight+cnt)-weight;dfs2(k,0);//搜索后半段cout<

第二种手写判重

#includeusing namespace std;typedef long long ll;const int N=110;int n,k;int cnt=1;ll w[N],m,weight[1<m) return;//假如已经大于了，则直接返回if(u==k)//假如搜到了最后一个{weight[cnt++]=s;//把这个值放进数组里来return;//这里不能少}dfs1(u+1,s);//假如不选这个数if(s+w[u]m) return;//假如已经大于了，则直接返回 if(u==n)//假如搜到了最后一个 { //下面二分有左边界，因为找刚好小于m的最大数int l=0,r=cnt-1;while(l>1;if(weight[mid]+s<=m) l=mid;else r=mid-1;} ans=max(ans,s+weight[l]);//更新一下答案 return;//这里不能少 }dfs2(u+1,s);//假如不选这个数if(s+w[u]>m>>n;for(int i=0;i>w[i];//从大到小排序sort(w,w+n);reverse(w,w+n);k=n/2+1;//对半分开搜索dfs1(0,0);//搜索前半段，打表出来存进数组里头// 判重 去重int t = 1;for (int i = 1; i < cnt; i++)if (weight[i] != weight[i - 1])weight[t++] = weight[i];cnt = t;dfs2(k,0);//搜索后半段cout<

3.IDA*

找估计函数，在枚举步数，用估计函数+当前步数来剪枝，大大提高效率，前提是答案的层数小

1.排书

题目https://www.acwing.com/problem/content/182/

#includeusing namespace std;const int N=20;int n;int q[N],w[5][N];int f()//用来计算估计函数{int totol=0;//算位置不符合的总个数for(int i=0;imax_depth) return false;//假如当前步数加上估计函数大于最大步数了，说明不符合if(f()==0) return true;//假如估计函数为0，也就是正确答案了，则直接返回truefor(int len=1;len<=n;len++)//枚举需要更改的长度for(int l=0;l+len-1<n;l++)//枚举左边界{int r=l+len-1;//右边界for(int k=r+1;k<n;k++)//枚举需要跟右边那个位置交换{memcpy(w[depth],q,sizeof q);//把上一层的状态复制过来int x=l;//下面进行这一段跟右边的位置交换for(int y=r+1;y<=k;y++,x++) q[x]=w[depth][y];for(int y=l;y>T; while(T--) { cin>>n; for(int i=0;i>q[i]; int depth=0;//枚举所用的步数 while(depth<5&&!dfs(0,depth)) depth++;//假如所用步数不能排好书，则步数++ if(depth<5) cout<<depth<<endl; else puts("5 or more"); } return 0;}

2.回转游戏

题目https://www.acwing.com/problem/content/183/

#includeusing namespace std;const int N=24;int n;int q[N],path[110];//分别为八个方向的位置int op[8][7]={{0,2,6,11,15,20,22},{1,3,8,12,17,21,23},{10,9,8,7,6,5,4},{19,18,17,16,15,14,13},{23,21,17,12,8,3,1},{22,20,15,11,6,2,0},{13,14,15,16,17,18,19},{4,5,6,7,8,9,10}};int unop[8]={5,4,7,6,1,0,3,2};//八个方向的反操作，避免往上拉了，又往下拉，等于没操作int cenctr[8]={6,7,8,11,12,15,16,17};//中心的8个位置int f()//算估计函数{static int temp[4];//静态数组节省空间memset(temp,0,sizeof temp);//清空for(int i=0;i<8;i++) temp[q[cenctr[i]]]++;//记录中间那个数出现的最多int m=0;for(int i=1;i<=3;i++) m=max(m,temp[i]);//求一下出现最多的数的个数return 8-m;//返回最少需要操作的次数，也就是8-m}void operate(int x)//进行把数组第一个往上拉去最后一个，其他往前一个位置的操作{int t=q[op[x][0]];for(int i=0;imax_depth) return false;//假如估计函数+目前步数已经大于最大步数了，则返回falseif(f()==0) return true;//假如已经排好了，则返回truefor(int i=0;i>q[0],q[0]){for(int i=1;i>q[i];int depth=0;//枚举需要走的步数while(!dfs(0,depth,-1)) depth++;//假如改步数不符合，则步数++if(!depth) printf("No moves needed");else{for(int i=0;i<depth;i++) printf("%c",path[i]+'A');//输出路径}printf("\n%d\n",q[6]);//输出中心的数字} return 0;}