dfs剪枝

1.可行性剪枝 木棒

首先思考搜索的过程：遍历可能的所有长度，dfs判断能否拼出。

在dfs的过程中，如果当前已经拼成的木棒数量等于长度下对应的木棒数量，则返回true，如果无法拼出，则返回false。

接下来开始剪枝。

首先思考搜索顺序：我们应该优先放置长度较长的木棒。

比较关键的剪枝是可行性剪枝，比较难想：

①如果一根木棒放在某个位置不成功，那么和它等长的所有木棒放在该位置都不会成功。

②如果一根木棒放在某根木棍的第一个位置不成功，那么接下来无论它放在哪个位置都不可能成功。因为当它放在第一个位置不成功时，说明后面的所有木棒的组合都无法和它拼出一条木棍，而我们越往后选择木棒，可以选择的木棒只会变少，更不可能和它组合拼出一条木棍了。

③如果一根木棒放在某根木棍的最后一个位置成功，但是接下来的某一根木棍无法拼出，那么接下来它无论放在哪个位置都不可能拼出答案。可以用反证法证明，假设它放在最后一个位置是成功的，我们可以用两根更短的木棒x、y替代当前木棒i，如果可以得出一种成功的方案，在这种方案中，因为i和x+y是等长的，我们一定可以通过交换把i换到某根木棍的最后一个位置，这和已知的一定不成功矛盾了。

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=70; int a[N]; int n; bool st[N]; bool cmp(int x,int y) { return x>y; } bool dfs(int u,int curlen,int taglen,int tagcnt) { if(curlen==taglen) return dfs(u+1,0,taglen,tagcnt); if(u>=tagcnt) return true; for(int i=1;i<=n;i++) { if(st[i]) continue; if(curlen+a[i]<=taglen) { st[i]=1; if(dfs(u,curlen+a[i],taglen,tagcnt)) return true; st[i]=0; if(curlen+a[i]==taglen) return false; int j=i; while(a[i]==a[j]) j++; i=j-1; if(curlen==0) return false; } } return false; } int main() { while(cin>>n&&n!=0) { int sum=0; memset(st,0,sizeof(st)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } sort(a+1,a+1+n,cmp); for(int i=a[1];i<=sum;i++) { if(sum%i==0) { if(dfs(0,0,i,sum/i)) { printf("%d\n",i); break; } } } } } 2.迭代加深 加成序列

170. 加成序列 - AcWing题库

简言之，就是找到一个单调递增的序列，其中最大的数字是n，且每个数字由它及它之前的任意两个数字相加而成。

按照最暴力的方式搜索，我们的树是这样的：

左边的两棵树明显不是最优答案，但是我们一定会将它搜到底，再去搜索其他的方案，我们在完全不可能的子树中浪费了很多时间。

对于这样的情况，我们可以用迭代加深来进行优化。

在每一次搜索时，我们提前设置好本次搜索最多搜到哪一层，如果在当前层搜到了，就不需要往下一层走。

#include<iostream> using namespace std; const int N=110; int n; int path[N]; bool dfs(int u,int depth)//在填path第u个位置上的数，当前最大层数depth { if(path[u-1]==n) return true; if(u>depth) return false; bool st[N]={0}; for(int i=u-1;i>=1;i--) for(int j=i;j>=1;j--) { int t=path[i]+path[j]; if(t>path[u-1]&&u<=n) { path[u]=t; st[u]=1; if(dfs(u+1,depth)) return true; } } return false; } int main() { while(cin>>n&&n!=0) { path[1]=1; int depth=1; while(!dfs(2,depth)) depth++; for(int i=1;i<=depth;i++) printf("%d ",path[i]); printf("\n"); } } 3.双向dfs 送礼物

171. 送礼物 - AcWing题库

这一题乍一眼看是01背包，但是w范围太大了。

考虑dfs，一共有种状态，这里n是46，时间复杂度超了。

这里可以双向dfs，我们先求出前n/2个物品中合理的所有可能（记录在a数组中），再对后n/2个物品进行组合，当组合出的情况合理时，我们找到a数组中加上当前值离w最近的值，也就是说，在a数组中找到小于（w-当前值）的最大值，这个过程可以用二分。最后的时间复杂度就是2**log(n/2)。

#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=50; int w,n,k; int a[N]; int weight[1<<24],cnt=1; ll res=0; void dfs1(int u,ll s) { if(u>k) { weight[cnt++]=s; return; } dfs1(u+1,s); if((ll)s+a[u]<=w) dfs1(u+1,(ll)s+a[u]); } void dfs2(int u,ll s) { if(u>n) { int l=0,r=cnt-1; while(l<r) { int mid=(l+r+1)>>1; if(weight[mid]<=w-s) l=mid; else r=mid-1; } res=max(res,s+weight[l]); return; } dfs2(u+1,s); if((ll)a[u]+s<=w) dfs2(u+1,(ll)s+a[u]); } int main() { scanf("%d%d",&w,&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); k=n/2; dfs1(1,0); cnt=unique(weight,weight+cnt)-weight; sort(weight,weight+cnt); dfs2(k+1,0); printf("%lld",res); } 4.IDA* 排书

180. 排书 - AcWing题库

IDA*其实是可行性剪枝和迭代加深的结合，在迭代加深的基础上，加上一个类似于A*的代价函数就好了。

在本题中，我们可以发现，当我们每次执行插入操作时，会改变三对相邻结点的顺序。

也就是说，每次进行插入操作，我们最多使当前状态向前走三步。于是，我们的代价函数可以是，计算当前距离终点还差几步tot，则至少还需要（tot+2）/3，即（tot/3）向上取整的代价。

#include<iostream> #include<cstring> using namespace std; const int N=20; int n; int a[N]; int w[5][N]; int f() { int tot=0; for(int i=1;i<n;i++) if(a[i+1]!=a[i]+1) tot++; return (tot+2)/3; } bool dfs(int u,int depth) { if(u>depth||f()+u>depth) return false; if(f()==0) return true; for(int len=1;len<=n;len++) for(int l=1;l+len-1<=n;l++) { int r=l+len-1; for(int k=r+1;k<=n;k++) { memcpy(w[u],a,sizeof(a)); int y=l,x; for(x=r+1;x<=k;x++,y++) a[y]=w[u][x]; for(x=l;x<=r;x++,y++) a[y]=w[u][x]; if(dfs(u+1,depth)) return true; memcpy(a,w[u],sizeof(a)); } } return false; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int depth=0; while(depth<5&&dfs(0,depth)==0) depth++; if(depth>=5) printf("5 or more\n"); else printf("%d\n",depth); } } 回转游戏

181. 回转游戏 - AcWing题库

因为棋盘的形状比较奇怪，我们可以用一个8*7的数组来记录每一个操作改变的对应行。

int g[N][N]={ {1,3,7,12,16,21,23}, {2,4,9,13,18,22,24}, {11,10,9,8,7,6,5}, {20,19,18,17,16,15,14}, {24,22,18,13,9,4,2}, {23,21,16,12,7,3,1}, {14,15,16,17,18,19,20}, {5,6,7,8,9,10,11} };

我们的代价函数可以是，统计一下当前中心8个数中出现最多的数字出现了几次，则我们还需要的最少代价就是8-最大出现次数。

int f() { int cnt[4]={0}; for(int i=0;i<8;i++) cnt[q[center[i]]]++; sort(cnt,cnt+4); return 8-cnt[3]; }

这题比较困扰我的是数据的处理上，在用数组打表了之后，我们操作时，每一行在棋盘上对应的编号是不变的，但是编号对应的数字需要改变，因此是将某一行的数字进行移动。

也就是说，每次操作是将某一行的q值进行改变，而不是g值。

#include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; const int N=8; int g[N][N]={ {1,3,7,12,16,21,23}, {2,4,9,13,18,22,24}, {11,10,9,8,7,6,5}, {20,19,18,17,16,15,14}, {24,22,18,13,9,4,2}, {23,21,16,12,7,3,1}, {14,15,16,17,18,19,20}, {5,6,7,8,9,10,11} }; int opposite[N]={5,4,7,6,1,0,3,2}; int center[N]={7,8,9,12,13,16,17,18}; int q[3*N+5]; vector<int> path; int f() { int cnt[4]={0}; for(int i=0;i<8;i++) cnt[q[center[i]]]++; sort(cnt,cnt+4); return 8-cnt[3]; } void operate(int x) { int t=q[g[x][0]]; for(int i=0;i<6;i++) q[g[x][i]]=q[g[x][i+1]]; q[g[x][6]]=t; } bool dfs(int u,int depth,int last) { if(u>depth||u+f()>depth) return false; if(f()==0) return true; for(int i=0;i<8;i++) { if(last==opposite[i]) continue; operate(i); path.push_back(i); if(dfs(u+1,depth,i)) return true; operate(opposite[i]); path.pop_back(); } return false; } int main() { while(cin>>q[1]&&q[1]!=0) { for(int i=2;i<=24;i++) cin>>q[i]; path.clear(); int depth=0; while(dfs(0,depth,-1)==0) depth++; if(!depth) printf("No moves needed"); else for(int i=0;i<path.size();i++) { char c=path[i]+'A'; cout<<c; } printf("\n%d\n",q[7]); } }