acm必做50题的解题-搜索

《acm必做50题的解题-搜索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、POJ1011Sticks搜索+强剪枝（终于AC了，分享经验）这个题目是不是贪心的，我就是第一次用了贪心，一直WA，相当的悲剧，贪心错误的sample：715118884321，所以大家还是全部搜索。但是全部搜索必须剪枝，不然肯定是TLE的，而且本体属于强剪枝，少剪了也是TLE。经典搜索题，果然是到处充斥着剪枝才能过啊，我的代码离剪到极限还差很多题目给出一大堆小棍子的长度，需要把他们拼成几根长度相等的大棍子，求大棍子的最短长度看自己剪枝方法的效果时候，可以添设一个变量来记录递归次数如剪枝4：没有这个剪枝的情况下对以下数据需要40万次递归，

2、而加上这个剪枝后减少到了4万多次对数据：451532411188815324111888153241118881532411188815324111888#include#includeusingnamespacestd;intsticks[65];intused[65];intn,len;booldfs(inti,intl,intt)//i为当前试取的棍子序号,l为要拼成一根完整的棍子还需要的长度,t初值为所有棍子总长度{if(l==0){t-=len;if(t==0)returntrue;fo

3、r(i=0;used[i];++i);//剪枝1：搜索下一根大棍子的时候，找到第一个还没有使用的小棍子开始used[i]=1;//由于排序过，找到的第一根肯定最长，也肯定要使用，所以从下一根开始搜索if(dfs(i+1,len-sticks[i],t))returntrue;used[i]=0;t+=len;}else{for(intj=i;j0&&(sticks[j]==sticks[j-1]&&!used[j-1]))//剪枝2：前后两根长度相等时，如果前面那根没被使用，也就是由前面那根continue;//

4、开始搜索不到正确结果，那么再从这根开始也肯定搜索不出正确结果，此剪枝威力较大if(!used[j]&&l>=sticks[j])//剪枝3：最简单的剪枝，要拼成一根大棍子还需要的长度L>=当前小棍子长度，才能选用{l-=sticks[j];used[j]=1;if(dfs(j,l,t))returntrue;l+=sticks[j];used[j]=0;if(sticks[j]==l)//剪枝4：威力巨大的剪枝，程序要运行到此处说明往下的搜索失败，若本次的小棍长度刚好填满剩下长度，但是后break;//面的搜索失败，则应该返回上一层}}}

5、returnfalse;}boolcmp(constinta,constintb){returna>b;}intmain(){while(cin>>n&&n){intsum=0;for(inti=0;i>sticks[i];sum+=sticks[i];used[i]=0;}sort(sticks,sticks+n,cmp);//剪枝5：从大到小排序后可大大减少递归次数boolflag=false;for(len=sticks[0];len<=sum/2;++len)//剪枝6：大棍长度一定是所有小棍长度之和的因数

6、，且最小因数应该不小于小棍中最长的长度{if(sum%len==0){if(dfs(0,len,sum)){flag=true;cout<

7、起，要求转移的次数最少。解：其实根本不用搜索，一开始想搜索想了很久，上网找解题报告也没找到（这么水的一题竟然没有解题报告），于是开始自已想。其实碎片的排列只有二种情况：1.A0碎片没有放在原来的位置，而它原来的位置正好是空的。而A1碎片也刚好没有放在原来的位置，而b原来的位置之前一直被A0占领，同样还有A2碎片没有在原来位置，而其原来的位置之前一直被A1占领，以此递推直到Ai,没有碎片要放在Ai的位置为止。这种情况称为链。2.基本上同1一样，不过，一开始的时候A0的原来位置并不是空的，而是最后的那个Ai占领着，这种情况称为环。解决方法：1

8、。对于1，只需要从A0开始一个一个按顺序放到原来的位置上即可。2。对于2，只需要从环中的任何一个节点开始，先将这个节点放到从尾部开始数起的空位，然后以链的方式处理，最后再将这个节点的数放回到最