poj 1011 木棍

poj 1011 木棍

经典题啊经典题。

已知拖到 今天 才 写完。。

题目：
中文题，，就不翻译成英语了。。。

分析：
是一个搜索了。。
枚举木棍长度的每个可能【【最小就是最长的那根木棍】】
然后 拼当期那木棍 判断是否 可以拼成。
然后 时间比较紧张 需要 剪枝。

首先 最容易想到的是：
搜索的 长度必须是 和的因数

然后 最好是从大向小搜。为什么呢？
因为越小越灵活啊，，搜到最后越容易出结果。【【因为后面会好拼】】

再然后：
长度相等的棍子 不需要再搜 可以直接跳过

此次是在尝试第num+1个木棒的第一段，假设stick[j]为当前可以被使用的最长的木棍，如果此次组合失败，直接退出搜索，即退回到对第num个木棒的搜索。试想：失败说明现在使用stick[j]是不可行的，那么以后无论什么时候使用stick[j]都是不可行的，因为以后再处理stick[j]时可使用的木棍一定是当前可使用的木棍的子集，在更多木棍选择的情况下都不能组合成功，那么，在更少木棍选择的情况下一定不能组合成功。【【【似不似特别好。我也直接粘的~

有时间再写一遍吧。。

感觉真是 晕 but 因缺思婷。。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
//by mars_ch
int n,sum,maxx,aim,nn;
int l[65];
int vis[65];
bool cmp(int a,int b)
{return a>b;
}
bool dfs(int num,int pos,int len)     // 拼了几根，，搜到第几根，，还剩多少length需要拼成当前长度 
{if(num==nn) return 1;    //如果拼成了  的话就  ok~ for(int i=pos+1;i<=n;i++)      //搜到第几根棍子往下 {if(vis[i]== 1 || (i>1 && vis[i-1] == 0 && l[i]==l[i-1]))     // 上一根  不能用，这根跟上根还相等 能不用 continue;else {if(len == l[i]){vis[i]=1;if(dfs(num+1,0,aim)== 1) return 1;vis[i]=0;return 0;}if(len>l[i]){vis[i]=1;if(dfs(num,pos+1,len-l[i]) == 1) return 1;vis[i]=0;if(len == aim) return 0;      //如果他是第一个木棍。他当前 这个都拼不成。 那么后面肯定也用不到它。。怎可以省下一根不用呢》 }           }} return 0;   
}
int main()
{while(scanf("%d",&n) && n!=0){int flag=0;memset(l,0,sizeof(l));maxx=0;sum=0;for(int i=1;i<=n;i++){scanf("%d",&l[i]);sum+=l[i];maxx=max(maxx,l[i]);}sort(l+1,l+n,cmp);for(aim=maxx;aim<=sum;aim++){if(sum % aim ==0){nn=sum/aim;memset(vis,0,sizeof(vis));    if(dfs(0,0,aim) == 1) {flag=1;printf("%dn",aim);break;}}}//  if(flag == 0) printf("impossble");}return 0;
}