1.迭代加深

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

加成序列

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

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n;
int path[N];
bool dfs(int u,int depth)//第一个是元素个数，第二个是当前的深度
{if(u>depth) return  false;//假如元素大于深度，说明不可能了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<=path[u-1]) continue;//假如已经枚举过或者和大于n或者不符合后一个数比前一个数小，则跳过st[s]=true;//标记这个数已经用过path[u]=s;//这个数放进数组里if(dfs(u+1,depth)) return true;//继续搜索下一个数}return false;
}
int main()
{path[0]=1;//规定第一个数是1while(cin>>n,n){int depth=1;//枚举深度，大概知道答案在比较近的一层，所以不枚举宽度while(!dfs(1,depth)) depth++;//假如这个深度不符合，则加1for(int i=0;i<depth;i++) cout<<path[i]<<' ';//输出答案puts("");}return 0;
}

2.双向dfs

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

送礼物

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
int n,k;
int cnt=1;
ll w[N],m,weight[1<<25],ans;
void dfs1(int u,ll s)
{if(s>m) return;//假如已经大于了，则直接返回if(u==k)//假如搜到了最后一个{weight[cnt++]=s;//把这个值放进数组里来return;//这里不能少}dfs1(u+1,s);//假如不选这个数if(s+w[u]<=m) dfs1(u+1,s+w[u]);//假如满足条件选这个数
}
void dfs2(int u,ll s)
{if(s>m) return;//假如已经大于了，则直接返回if(u==n)//假如搜到了最后一个{//下面二分有左边界，因为找刚好小于m的最大数int l=0,r=cnt-1;while(l<r){int mid=l+r+1>>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) dfs2(u+1,s+w[u]);//假如符合条件选这个数
}
int main()
{cin>>m>>n;for(int i=0;i<n;i++) cin>>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<<ans<<endl;return 0;
}

第二种手写判重 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
int n,k;
int cnt=1;
ll w[N],m,weight[1<<25],ans;
void dfs1(int u,ll s)
{if(s>m) return;//假如已经大于了，则直接返回if(u==k)//假如搜到了最后一个{weight[cnt++]=s;//把这个值放进数组里来return;//这里不能少}dfs1(u+1,s);//假如不选这个数if(s+w[u]<=m) dfs1(u+1,s+w[u]);//假如满足条件选这个数
}
void dfs2(int u,ll s)
{if(s>m) return;//假如已经大于了，则直接返回if(u==n)//假如搜到了最后一个{//下面二分有左边界，因为找刚好小于m的最大数int l=0,r=cnt-1;while(l<r){int mid=l+r+1>>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) dfs2(u+1,s+w[u]);//假如符合条件选这个数
}
int main()
{cin>>m>>n;for(int i=0;i<n;i++) cin>>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<<ans<<endl;return 0;
}

3.IDA*

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

 1.排书

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

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
int q[N],w[5][N];
int f()//用来计算估计函数
{int totol=0;//算位置不符合的总个数for(int i=0;i<n-1;i++)if(q[i]!=q[i+1]-1)totol++;return (totol+2)/3;//因为每次交换能更改三个位置的后缀，我们算他改的都是正确的则就除以三，但是实际肯定是小了的
}
bool dfs(int depth,int max_depth)//depth是当前已执行的步数，max_depth是最大步数
{if(f()+depth>max_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<=r;y++,x++) q[x]=w[depth][y];//进行下一步，假如下一步可以符合答案，则链式返回trueif(dfs(depth+1,max_depth)) return true;memcpy(q,w[depth],sizeof q);//把更改后的这一层q复制到w这一层中，供下一层使用}}return false;//反之返回失败
}
int main()
{int T;cin>>T;while(T--){cin>>n;for(int i=0;i<n;i++) cin>>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/

#include<bits/stdc++.h>
using 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;i<6;i++) q[op[x][i]]=q[op[x][i+1]];q[op[x][6]]=t;
}
bool dfs(int depth,int max_depth,int last)//depth是当前步数，max_depth是最大步数，last是上一步的操作
{if(depth+f()>max_depth) return false;//假如估计函数+目前步数已经大于最大步数了，则返回falseif(f()==0) return true;//假如已经排好了，则返回truefor(int i=0;i<8;i++)//枚举8个操作if(unop[i]!=last)//返回操作了上又操作下，等于没操作{operate(i);//操作ipath[depth]=i;//把当前路径标记为i操作的if(dfs(depth+1,max_depth,i)) return true;//假如下一步操作是true，则返回trueoperate(unop[i]);//恢复现场，也就是反向操作一下}return false;//找不到合法答案
}
int main()
{while(cin>>q[0],q[0]){for(int i=1;i<N;i++) cin>>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;
}