1.迭代加深
顾名思义说明迭代的层数逐渐加深，这样做法有点像bfs的做法层层突出，符合的题型是答案在层数较低的那一层里
加成序列
#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&&depth==u) 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;//规定第一个数是1 while(cin>>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，搜索前半段与后半段
送礼物
#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; }
3.IDA*
找估计函数，在枚举步数，用估计函数+当前步数来剪枝，大大提高效率，前提是答案的层数小
1.排书
#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，也就是正确答案了，则直接返回true for(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]; //进行下一步，假如下一步可以符合答案，则链式返回true if(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.回转游戏
#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;//假如估计函数+目前步数已经大于最大步数了，则返回false if(f()==0) return true;//假如已经排好了，则返回true for(int i=0;i<8;i++)//枚举8个操作 if(unop[i]!=last)//返回操作了上又操作下，等于没操作 { operate(i);//操作i path[depth]=i;//把当前路径标记为i操作的 if(dfs(depth+1,max_depth,i)) return true;//假如下一步操作是true，则返回true operate(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; }
