Acwing167. 木棒
题目链接：167. 木棒 - AcWing题库
标签：dfs+剪枝
思路1：
同小猫过河，每次选一根短木条，放在前面没有拼好的木棍中，或者新开一条木棍。
剪枝：
1.拼的木棍条数越多，每条木棍的长度越短，且最多可以拼成n条木棍（即每根木条一样长）。先用总长度对期望的条数取余，如余数为0再dfs。
2.如果当前搜索拼成木棍的条数已经超过期望的条数，return false；
3.如果有木条长度大于期望拼成木棍的长度，return false；
结果：TLE...
代码：
#include
#include
#include
using namespace std;const int N = 65;int n;
int sum[N],l[N];
int s;bool dfs(int u,int cnt,int len)
{if(u>n && cnt*len==s) return true;else if(cnt*len>s) return false;else if(u>n) return false;else if(l[u]>len) return false;for(int i=1;i<=cnt;i++){if(sum[i]+l[u]<=len){sum[i]+=l[u];if(dfs(u+1,cnt,len)) return true;sum[i]-=l[u];}}sum[cnt+1]=l[u];return dfs(u+1,cnt+1,len);
}int main()
{while(cin>>n && n){s=0;memset(sum,0,sizeof sum);for(int i=1;i<=n;i++){cin>>l[i];s += l[i];}sort(l+1,l+n+1,greater());for(int i=n;i>=1;i--){if(s%i==0){if(dfs(1,0,s/i)) {cout< 思路2：
对所有木条遍历，先拼好一根木棍，再拼下一条木棍。
剪枝优化：
1.如果这条木棍没有拼好，return false；
2.如果这条木棍拼好了，但剩余的木条无法拼成木棍，return false;
3.如果拼当前木棍时，放入长度为fail的木条没有拼成功，那么就不要再对长度为fail的木棍进行搜索。
4.对木条从大到小排序，先放长度大的木条。
代码：
#include
#include
#include
using namespace std;const int N = 100;int n;
int a[N],sum,len;
bool vis[N];bool dfs(int u,int cab,int last)
{if(u*len==sum) return true;if(cab==len) return dfs(u+1,0,1);int fail=0; //当前插入长度为fail的木棍失败，那么选择下一个木棍时，若该木棍的长度为fail，那么将不搜索。for(int i=last;i<=n;i++){if(!vis[i] && cab+a[i]<=len && a[i]!=fail){vis[i]=true;if(dfs(u,cab+a[i],i+1)) return true;vis[i]=false;fail=a[i];//目前已经拼好u-1 / u 个木棍，但剩余的木条无法拼成木棍，可以直接return falseif(cab==0 || cab+a[i]==len) return false;}}return false;
}int main()
{while(cin>>n && n){sum=0;memset(vis,0,sizeof vis);for(int i=1;i<=n;i++) cin>>a[i] , sum+=a[i];sort(a+1,a+n+1,greater());for(int i=n;i>=1;i--)//i为原始木棍的个数{if(sum%i==0){len = sum/i;if(dfs(0,0,0)){cout< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！