题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
先写一个暴力……
暴力最好写了，然后再考虑剪枝
这是暴力：记录一下当前那根大木棍已经接了多长，已经接了多少根大木棍和一根大木棍应该有多长。
当然暴力也可以加一个简单的剪枝：记录一下总长度，如果当前枚举的一根大木棍的应有长度不能整除总长度那就不搜。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
void dfs(int seq,int nowlen,int steps) { if (nowlen==sum/seq && steps<seq-1) { dfs(seq,0,steps+1); return; } if (steps==seq-1 && nowlen==sum/seq) { cout<<sum/seq; exit(0); } for (int i=1;i<=len;i++) if (!used[i] && nowlen+a[i]<=sum/seq) { used[i]=true; dfs(seq,nowlen+a[i],steps); used[i]=false; } } int main() { scanf("%d",&len); int cache,len2=len,c1=1; for (int i=1;i<=len2;i++) { scanf("%d",&cache); if (cache>50) { len--; continue; } a[c1]=cache; sum+=a[c1]; minlen=min(minlen,a[c1]); c1++; } for (int i=len;i>=1;i--) if (sum%i==0) { memset(used,0,sizeof(used)); dfs(i,0,0); } } |
然后剪枝：
1.我们按长度排序，如果当前正在拼一根新的木棍，而且最大的一根小木棍加上当前的长度（应该是0）都不能满足枚举到的当前大木棍长度那就剪掉。
2.还是上述操作，不过是剪掉：整整一根小木棍都比当前枚举到的大木棍的长度长的情况（那样显然无解）
3.还是排序之后，记录一下上次尝试了哪一根小木棍（也就是长度）如果这次枚举到的小木棍的长度和上次相等那么也剪掉。
4.如果搜的目标是拼最后一根大木棍了，而且最后还无解，回溯回来了，那这组直接放弃。
就这些？
对，一共就这么六个剪枝 （排序&暴力的剪枝&1234）
试试刚刚才意识到的高亮操作
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<cstdio> #include<cstring> #include<iostream> #include<string> #include<cmath> #include<algorithm> #include<iterator> #include<utility> using namespace std; int len,a[100]={0}; int sum=0,divide,seq; bool used[100]={false}; void dfs(int nowlen,int steps,int pos) { if (steps==seq) { printf("%d\n",divide); exit(0); } if (nowlen==0) { while (used[pos]) pos--; if (a[pos]>divide) return; } int pre=-1; for (register int i=pos;i>=1;i--) if (!used[i] && a[i]!=pre && a[i]+nowlen<=divide) { used[i]=true; pre=a[i]; if (nowlen+a[i]==divide) { dfs(0,steps+1,len); used[i]=false; return; } else { dfs(nowlen+a[i],steps,i-1); if (nowlen==0) { used[i]=false; return; } used[i]=false; } } } int main() { scanf("%d",&len); int cache,len2=len,c1=1; for (int i=1;i<=len2;i++) { scanf("%d",&cache); if (cache>50) { len--; continue; } a[c1]=cache; sum+=a[c1]; c1++; } sort(a+1,a+len+1); for (int i=a[len];i<=sum;i++) if (sum%i==0) { divide=i;//每段的长度 seq=sum/i;//段数 dfs(0,0,len); } } |