乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出文件仅一行，表示要求的原始木棍的最小可能长度
普通DFS不加last剪枝=44分 加last剪枝=54分 加神TM剪枝=100分 蛤蛤
#include <cstdio> #include <cstring> #include <algorithm> #include <functional> #define maxn 520 #define INF 100000000 using namespace std; int n,L,last=1,s[maxn],suml=0,maxl=0,minl=INF,c=0; bool vis[maxn]; bool dfs(int cnt,int len){//剩余cnt根木棍，拼到当前还差len的长度 if(cnt==0&&len==0) return 1;//木棍不剩且刚好拼到目标长度就得到答案 int x=1;//初始化木棍从最长的开始试拼 if(len==0) len=L;//如果上一次刚好拼完一整根L，归零重新开始拼 if(len!=L) x=last;//last保存上一次是用s[last]这根木棍来减少len的，那么本次搜索就不必选比s[last]更长的木棍 //这是因为在尝试拼这一根木棍的时候，s[last]以前的都已经尝试过了 //如果说已经开始拼新的一根木棍了，就要从头开始搜没用过的了 for(int i=x;i<=n;i++){ if(vis[i]||s[i]>len) continue;//如果已经被占用，跳过 if(i>=1&&!vis[i-1]&&s[i]==s[i-1]) continue;//如果相同长度的不能用，跳过 vis[i]=1; last=i; if(dfs(cnt-1,len-s[i])) return 1; vis[i]=0; if(len==L||s[i]==len) return 0;//这步很机智啊，如果开始拼新木棍了，那么任何没有被选过的木棍都要能被选进去才行 //如果有一根木棍刚好可以填满，之后却爆炸了，那肯定也没解 //加上这个剪枝瞬间从50分到100分啊... } return 0; } int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); int temp; for(int i=1;i<=n;i++) { scanf("%d",&temp); if(temp>50) continue; else { s[++c]=temp; suml+=s[c]; } } n=c; sort(s+1,s+1+n,greater<int>()); for(L=s[1];L<=suml/2;L++){ if(suml%L!=0) continue;//如果目标长度不是sum的因数就可以跳过了 memset(vis,0,sizeof(vis)); if(dfs(n,L)){ printf("%d",L); break; } } if(L>suml/2) printf("%d",suml); return 0; }转载于:https://www.cnblogs.com/leotan0321/p/6081381.html
