木棒AcWing167(DFS+剪枝)

题目

题目分析

给出不同长度的木棒，这些木棒是由相同长度的木棒剪断而成，求出原来未剪断的木棒长度。

解题思路

我们枚举一个未剪断长度length，每次利用这个length去dfs，判断该长度是否可行。

DFS详解

如果去dfs呢?

题目范围时64个木棒，如果不进行剪枝，那么复杂度为64的64次幂，这个复杂度肯定无法通过。

所以dfs一定要进行多重剪枝

优化一

首先对搜索顺序进行优化，想一想，我们在拼凑一根完整的木棒时，先放一根大的木棒在搭配几根小的木棒，这样dfs去搜的方案数少还是先放几根小木棒所搜得的方案少呢?

答案肯定是先放大的木棒搜得的方案少，因为当我确定一个大的长度后，后面搭配的余量就比较少，能选择的方案也少。这就是优化搜索顺序

优化二

在索搜的时候如果当前木棒中某一长度搜索失败，那么后续相同长度继续向下dfs，那么他的结果肯定同样失败。仔细想一想dfs特点，比如棋盘问题，当从某个点向下dfs时这个点肯定会把所有的结果返回，如果这个点得不到想要的结果，那么你从其他点在经过这个点在继续搜，肯定结果都是相同的。

优化三

如果当前木棒放在开头返回结果失败，那么这个枚举的length肯定失败。

证明如下

优化四

如果当前木棒放在结尾返回结果失败，那么枚举的length肯定失败

证明和上图同理

细节

这道题要注意，当枚举木棒时必须不能枚举重复序列，也就是不能是全排列的形式，因为全排列123与132都是同一根木棒没有任何意义，所以要在dfs过程中加入起始遍历变量strart，这样保证每次枚举时递增，这样就不会造成重复。

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7fusing namespace std;
typedef pair<int,string> PII;
const int N=1e2+10;int  n,m,ans;
int vis[N];
int w[N];
int length,sum;
bool cmp(int x,int y) {return x>y;
}bool dfs(int u,int cur,int start) {//当前为第u根木棒，第u根不帮长度，从第几个开始枚举if(u*length==sum) return true;//当前length成立if(cur==length)return dfs(u+1,0,0);//枚举下一根木棒for(int i=start; i<n; i++) {if(vis[i]||cur+w[i]>length)continue;//可行性优化剪枝vis[i]=1;if(dfs(u,cur+w[i],i+1))return true;//向下dfsvis[i]=0;//dfs当前第u根木棒为i不成立时//放在开头失败 if(!cur)return false;//放在结尾失败 if(cur+w[i]==length) return false;//放在中间失败 //后面有连续相同的长度一定不成立int j=i;while(j<n&&w[j]==w[i])j++;i=j-1;}return false;
}int main() {while(cin>>n,n) {memset(vis,0,sizeof(vis));sum=0;for(int i=0; i<n; i++)cin>>w[i],sum+=w[i];sort(w,w+n,cmp);//先可大的拿这样减少方案数量length=1;while(true) {if(sum%length==0&&dfs(0,0,0)) {cout<<length<<endl;break;}length++;}}return 0;
}