【Uva 307】Sticks

【Link】:

【Description】



给你最多n个棍子;

(n< = 64)

每根棍子长度(1..50)

问你这n根棍子,可以是由多少根长度为x的棍子分割出来的;

x要求最小

【Solution】



首先,将各根棍子的长度求和->sum

最后的长度x肯定是sum的因子;

则枚举x从各根棍子长度的最大值sum作为因子;

枚举量假设为len;

然后一直用剩余的棍子去凑这个长度len

凑够了,就重新选择剩下的棍子,继续凑len;

剪枝:

1.还需要凑的量为len,但是尝试用完某根棍子之后,无法凑够,则直接return,因为表示有一根棍子不能够被加入到最后的答案中

2.剩余的棍子长度为sum,然后发现第一根尝试的棍子不能凑够,同理也退出

3.一根棍子用了之后,发现不行,则不再用这根棍子凑了,把相同的棍子跳过

4.从大到小排序,这样剪枝的效果会快一些出现



【NumberOf WA】



1



【Reviw】



凑够一根,然后继续凑;

(再从1开始);

记录之前用过哪一根;

没凑够的话,就从下一根根子开始;



【Code】

#include <cstdio>
#include <algorithm>
using namespace std; const int N = 64; int l[N+20],n,sum,now,vis[N+20]; bool dfs(int pre,int need,int rest){
if (rest==0) return true; for (int i = pre;i <= n;i++)
if (!vis[i] && l[i]<=need){
vis[i] = 1;
if (l[i]==need && dfs(1,now,rest-l[i]))
return true;
else if ( dfs(i+1,need-l[i],rest-l[i]))
return true;
vis[i] = 0;
if (rest==sum) return false;
if (need==now) return false;
while (i+1<=n && l[i+1]==l[i]) i++;
} return false;
} int main(){
//freopen("F:\\rush.txt","r",stdin);
while (~scanf("%d",&n)){
if (n==0) break;
sum = 0;
for (int i = 1;i <= n;i++)
scanf("%d",&l[i]),sum+=l[i];
for (int i = 1;i <= n;i++) vis[i] = 0;
sort(l+1,l+1+n);
reverse(l+1,l+1+n);
int ans = sum;
for (now = l[1];now < sum;now++)
if (sum%now==0){
if (dfs(1,now,sum)){
ans = now;
//printf("%d\n",now);
break;
}
}
printf("%d\n",ans);
}
return 0;
}
上一篇:Sticks(UVA - 307)【DFS+剪枝】


下一篇:一行代码轻松搞定各种IE兼容问题,IE6,IE7,IE8,IE9,IE10