Mayflyyh
Mayflyyh
MayFlyyh's Blog
POJ 1011 Sticks

现在有n根木棍,然后需要把它们拼成同样长度的木棍,问满足这个条件的最短的长度是多少?


搜索一下,显然长度之和应该能整除木棍数量,用这个数去看木棍能不能达成

有几个剪枝,先用桶排序,然后每次算的时候从大向小装,记一下装到的长度l,如果没有拼好这个木棍就接着l开始,如果拼好了就开始新的木棍从最大的那个长度开始。(想一想觉得还是很妙的)还有一个神奇的剪枝就是说如果放入了这个木棍,使这个木棍刚好拼好一个完整的棍或者这个木棍使第一个棍,那就不用再往下枚举长度了。因为枚举这个木棍之后的DFS已经把往下枚举的情况考虑过了!
(说的有点啰嗦了


\#include<iostream> #include<cstdio> #include<cstring> #include<string> #define inf 0x3f3f3f3f const int N = 100; int S[N],sum,max=-inf,flag,min=inf,n,nn; inline int dfs(int cnt,int now,int sum,int m){ if(flag) return flag; if(cnt==0){ printf("%d\n",sum); flag=1; } if(now==sum){ dfs(cnt-1,0,sum,max); } for(int i=m;i>=min;--i){ if(!S[i]||i+now>sum) continue; S[i]--; dfs(cnt,now+i,sum,i); S[i]++; if(now==0||now+i==sum) return 0; } } int main (){ while(scanf("%d",&n)&&n){ memset(S,0,sizeof(S)); sum=flag=0; for(int i=1;i<=n;++i){ int x; scanf("%d",&x); if(x<=50){ ++nn; min=std::min(min,x); max=std::max(max,x); S[x]++; sum+=x; } } n=nn; for(int i=min;i<=sum;++i){ if(sum%i!=0) continue; dfs(sum/i,0,i,max); } } return 0; }
本文链接:http://www.mayflyyh.com/archives/296
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      搜索      POJ 1011 Sticks
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

POJ 1011 Sticks
现在有n根木棍,然后需要把它们拼成同样长度的木棍,问满足这个条件的最短的长度是多少? 搜索一下,显然长度之和应该能整除木棍数量,用这个数去看木棍能不能达成 有几个剪枝,先用…
扫描二维码继续阅读
2018-07-16