《算法竞赛进阶指南》0x22dfs 经典搜索剪枝 第三遍做了
题目链接；http://poj.org/problem?id=1011
又是拼木棍呀，不过这次我是对他的剪枝原理完全弄清楚了，最后两条剪枝还真的是很难想到的。这次的剪枝中加入了一条：我们在某一跟木棍中拼接时，选择的木棍长度是递减的，这样就保证了搜索树中不会有重叠的部分，不过其实在木棍中，小木棒是无序的，可以用这个策略来证明剪枝的正确性，也就是说，拼第一根失败和拼最后一根失败之后，这个分支就不可能搜索到最终状态了。
代码：
#include<iostream> #include<cstdio> #include<string.h> #include<algorithm> using namespace std; #define maxn 100 int a[maxn],len,cnt,n; int vis[maxn]; int sum; int fail;//上一次拼接失败的木棍的长度 //last用来保证我们选择木棒的时候是按照递减的顺序选取的，防止搜索同样的状态空间 bool dfs(int stick,int cab,int last){//状态分别是当前在拼的是第几根木棍，当前木棍长度，开始选择的编号 if(stick==cnt+1)return true; if(cab==len)return dfs(stick+1,0,1);//新的木棍从第一根开始重新选择人拼接方案 fail=0; for(int i = last; i<=n;i++){ if(!vis[i] && cab+a[i]<=len && a[i]!=fail){//没用过并且能拼并且不是失败决策 vis[i]=1; if(dfs(stick,cab+a[i],i+1))return true; fail=a[i];//记录本次拼接失败的 木棒长度 vis[i]=0; if(cab==0 || cab+a[i]==len)return false; } } return false; } bool cmp(int &a,int &b){return a>b;} int main(){ while(cin>>n && n){ sum=0; int minlen=-0x7f7f7f7f; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum+=a[i]; minlen=max(minlen,a[i]); } sort(a+1,a+n+1,cmp);//降序，优先考虑决策少的方案 for(int i=minlen;i<=sum;i++){ if(sum%i)continue; len=i; cnt=sum/len; memset(vis,0,sizeof(vis)); if(dfs(1,0,1))break; } cout<<len<<endl; } }