首页 > 代码库 > 【poj1011】 Sticks
【poj1011】 Sticks
http://poj.org/problem?id=1011 (题目链接)
题意：给出一大堆小棍子的长度，需要把他们拼成几根长度相等的大棍子，求大棍子的最短长度。
solution
经典搜索题，剪枝剪到手软。
要得到最小的原始木棍长度，可以按照分段数的长度，依次枚举所有的可能长度L。每次枚举L时，dfs判断是否能用小木棍拼合出整数个L。如果不剪枝，就等着狂TLE吧。
最优性：
1.所有木棍的长度和一定能一定能整除大木棍长度L。
2.大木棍长度一定>=小木棍最长长度。
可行性：
3.一只长木棍肯定比几枝短木棍拼成同样长度的用处小，即短小的可以更灵活组合，所以可以对输入的所有木棍按长度排序。
4.当用木棍i拼合大木棍时，可以从第i+1后的木棍开始搜。因为根据剪枝3，i前面的木棍已经用过了。
5.用当前最长长度的木棍开始搜，如果拼不出当前设定的L，直接return。
6.相同长度的木棍不要搜多次。
7.判断搜到的几根木棍组成长度是否大于L，若大于，return。
8.判断当前剩下的木棍根数是否够拼的木棍数。
这里用了一个小小的技巧，函数互相调用，详情见代码。
代码：
// poj1011#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi 3.1415926535898#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int n,m,ans,length,a[100010],times,sum;bool b[100010],flag;void fit(int x);void dfs(int x,int len,int lev) { if (len==length) {fit(x+1);return;} for (int i=lev+1;i<=n;i++) if (!b[i] && len+a[i]<=length) {//剪枝5,7 if (n-times+1<ans-x) return;//剪枝8 b[i]=1; times++; dfs(x,len+a[i],i); times--; b[i]=0; int j=i; if (flag) return; while (i<n && a[i]==a[j]) i++;//剪枝6 if (i==n) return; if (i!=j) i--; }}void fit(int x) { int t; if (x>=ans) {flag=1;return;} for (int i=1;i<=n;i++) if (!b[i]) {t=i;break;}//剪枝4 b[t]=1; times++; dfs(x,a[t],t); times--; b[t]=0;}bool cmp(int a,int b) {return a>b;}int main() { while (scanf("%d",&n)==1) { if (n==0) break; sum=0;int maxl=0; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); maxl=max(maxl,a[i]); sum+=a[i]; } sort(a+1,a+1+n,cmp);//排序，剪枝3 memset(b,0,sizeof(b)); for (int i=n;i>=1;i--) { ans=i;length=sum/i; if (i==1) break; if (sum%i>0 || length<maxl) continue;//剪枝1,2 memset(b,0,sizeof(b)); times=0; flag=0; fit(1); if (flag) break; } printf("%d\n",sum/ans); } return 0;}
【poj1011】 Sticks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。