Poj 1011 &&UVA - 307 Sticks

牛客网 poj 1011

题目：

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0

Sample Output

6 5

题意：

一组等长木棍，砍成n份，现将n份重新组合，问原木棍的长度

题解：

dfs+剪枝 思路就是枚举每一种长度的可能，然后去验证是否成立 如果直接这样做肯定超时，我们需要优化，也就是剪枝 1.将原木棍的长度从小到大排列，并按照这个顺序进行搜索，原木棍的长度肯定在1~所有木棍之和范围内，也大于等于现所有木棍 2.如果我们探究第x个木块是否能匹配，如果与第i个木棍不能拼成假设长度，则和第i个木棍一样长的都不可以，这样可以跳过一批 3。如果对于一个木棍，找不到任何一个或多个木棍拼成预设原木棍长度，那说明该预设原木棍长度不存在，枚举下一个 对应代码部分就是

if(ret==a[i] || len==ret)break;

我是这么理解的： ret = = a[i]表示可以与a[i]，但是之后的木棍无法拼上，依旧不符合题意 len = = ret说明之后的任何一个木棍都拼不上

代码：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; int sum,a[100]; bool vis[100]; bool cmp(int a,int b){ return a>b; } int dfs(int len,int n,int stick,int ret) { if(stick==n && ret==0)//ret是代表的是以及一个棒已经拼的长度的 return len;//如果所有的棒都已经用完的话 if(ret==0)//这代表一个已经拼完啦！ ret=len; int i; for(i=0; i<n; i++) { if(vis[i]==true) continue; if(a[i]>ret) continue;//代表的是已经不满足题意了，直接要跳出大循环的 vis[i]=true; if(dfs(len,n,stick+1,ret-a[i])) //如果当前木棍与其他木棍拼成功 return len; vis[i]=false; if(ret==a[i] || len==ret)//最重要的剪枝，如果找不到任意一个枝和当前的枝进行匹配，则说明不可能对了，就直接跳出大循环的！ break; while(a[i]==a[i+1])//剪枝二，dfs的木块与第i根没有拼成的话，第i+1根和第i根长度相同的话也就拼不成了，剪去的 { printf("a[i]=%d,ret=%d,len=%d\n",a[i],ret,len); i++; } } return 0; } int main() { int i,j,n,k; while(1) { cin>>n; if(n==0) break; sum=0; for(i=0; i<n; i++) { cin>>a[i]; sum+=a[i]; } sort(a,a+n,cmp);//剪枝一，按照棍子从大到小排列的，然后直接舍弃总棍子太小的 for(i=a[n]; i<=sum; i++) { if(sum%i!=0) continue;//本来就不可以的啊 memset(vis,0,sizeof(vis)); k=dfs(i,n,0,i); //预设原木棍长度（固定的） 木棍总块数 所用木棍的数量 还需要拼的长度（不断变化） if(k!=0) break; } cout<<k<<endl; } return 0; }

另外 sort与qsort：

qosrt和sort我一直认为是qsort快，但也有说sort快的，我也是一脸懵逼

int num[maxn]; int cmp ( const void *a , const void *b ) { return *(int *)a - *(int *)b; } qsort(num,maxn,sizeof(int),cmp);