首页 > 代码库 > poj1011Sticks
poj1011Sticks
传说中的poj必做50题之一……
这是个传说中的搜索,
一开始以为,
只要棒子加起来等于假设的原始长度,
那么这几根选择的棒子就不用管了,
结果卡在第一个样例……
看了一下,发现,
代码把1,2,1,2合成一个棒子,
这样其他就凑不成3根长度为6的棒子了,
写了半天,发现思路错了,
这个问题不知道如何解决。
参考了以下地址的结题报告:
http://blog.csdn.net/lyy289065406/article/details/6647960
找到了一个解决办法,
就是当合成了一个新的棒子的时候,
就重新从第一个棒子开始枚举,
用没有用过的棒子,开始合成新的棒子。
写好代码之后,各种TLE……
于是又参考了上面那个解题报告,
找了个剪枝的办法,
就是如果碰到用某个棒子为第一个棒子合成新棒子
的时候,无法得到我想要的那种棒子,
就直接退栈并返回一个0表示这样不行,
写好之后,结果还是TLE,
于是继续剪了个枝
就是一开始给棒子递增排个序,
然后如果在合成棒子的中途发现
合成失败,用这根棒子得不到想要的那种棒子,
就把这个棒子标记一下,
如果在这次合成中再次碰到一样长度的棒子,
就直接舍弃。
又写好了……还是TLE。。。
我就不明白了……
再TLE,我真的没办法了。
又参考了结题报告,
发现给棒子递减排序就可以,
想了一下为毛,
是这样的,因为优先加入长度较长的棒子,
更容易在比较少的次数里合成想要的那种棒子。
我的代码如下,欢迎讨论:
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int stick[74],num_stk,sum_len; bool used[74]; bool cmp(int a,int b) { return a>b; } void init() { int i; sum_len=0; for(i=0;i<num_stk;i++) { scanf("%d",&stick[i]); sum_len+=stick[i]; } } bool dfs(int s,int nlen,int nnum,int olen) { int i,x=-1; if(nnum==num_stk) return 1; for(i=s;i<num_stk;i++) { if(used[i]||stick[i]==x||nlen+stick[i]>olen) continue; used[i]=1; if(nlen+stick[i]<olen) { if(dfs(i+1,nlen+stick[i],nnum+1,olen)) return 1; } else { if(dfs(0,0,nnum+1,olen)) return 1; } x=stick[i]; used[i]=0; if(nlen==0) return 0; } return 0; } void work() { int i; memset(used,0,sizeof(used)); sort(stick,stick+num_stk,cmp); for(i=stick[0];i+i<=sum_len;i++) { if(sum_len%i==0&&dfs(0,0,0,i)) { printf("%d\n",i); return; } } printf("%d\n",sum_len); } int main() { while(scanf("%d",&num_stk)&&num_stk!=0) { init(); work(); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。