题意大概是给你几根相同长度的绳子or木头，然后剪成几根，每段最大长度不超过50，最多剪成64根，然后问你，最开始没减的时候的最小长度是多少。 比如说 1 2 3 4 就是 1+4 2+3 两根 长度为5的剪得。
做这种需要剪枝的题，我的想法是，先不管超时，把容易想到的剪枝和整体思路写出来，然后再慢慢改。
就这道题而言， 比较好想的剪枝是先排序，和总长度除以目标长度要整除，不好想的是dfs里的剪枝，我觉得还是我练的少，要继续努力。 还有我测试了hduoj讨论区的几个样例，是比较慢的，应该还有剪枝的方法，希望大家能指教一下。
#include <iostream> //减后每一段绳子的最大长度为50，最多剪成64根 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int a[70],n; bool book[70],tag; bool cmp(int a, int b) //从大到小 { return a>b; } void dfs(int pos, int len, int ans, int num) //当前下标，当前长度，目标长度，已匹配根数 { if(tag) return; if(num == n)//表示全部符合 找到结果了 { tag = 1; return; } for(int i=pos; i<n; i++) { if(!book[i] && a[i]+len <=ans) { book[i] = 1; if(a[i] + len == ans) dfs(0,0,ans,num+1); else dfs(i+1,a[i]+len,ans,num+1); book[i] = 0; if(tag) return; if(len == 0) //剪枝： 如果到这一步了len还是0，说明当前的这一根没有能够匹配到，也就是会多出来，直接pass return; while(a[i+1] == a[i]) //剪枝：如果这根成功不了的话，那相同长度的也成功不了 i++; } } } int main() { while(scanf("%d",&n) != EOF && n) { int sum=0,ans; for(int i=0; i<n; i++) { scanf("%d",&a[i]); sum += a[i]; } sort(a,a+n,cmp); ans = a[0]; tag = 0; while(!tag) { while(sum % ans != 0) //剪枝： 总长度除以目标长度要整除 ans++; memset(book,0,sizeof(book)); dfs(0,0,ans,0); if(tag) break; ans++; } printf("%d\n",ans); //因为从小的开始找的，所以第一个找到的就是答案 } return 0; }