Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

绿色网站无广告
会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

POJ1011-Sticks

来源: 未知 分享至:

转载请注明出处:優YoU   http://user.qzone.qq.com/289065406/blog/1311647833

大致题意:

2011 POJ暑假集训题Problem EPOJ上有中文版

 

解题思路:

DFS+剪枝

 

POJ2362的强化版,重点在于剪枝

 

InitLen为所求的最短原始棒长,maxlen为给定的棒子堆中最长的棒子,sumlen为这堆棒子的长度之和,那么InitLen必定在范围[maxlensumlen]

 

根据棒子的灵活度(棒子越长,灵活度越低) DFS前先对所有棒子降序排序

 

剪枝:

1、  由于所有原始棒子等长,那么必有sumlen%Initlen==0

2、  若能在[maxlen,sumlen-InitLen]找到最短的InitLen,该InitLen必也是[maxlen,sumlen]的最短;若不能在[maxlen,sumlen-InitLen]找到最短的InitLen,则必有InitLen=sumlen

3、  由于所有棒子已降序排序,在DFS时,若某根棒子不合适,则跳过其后面所有与它等长的棒子;

4、  最重要的剪枝:对于某个目标InitLen,在每次构建新的长度为InitLen的原始棒时,检查新棒的第一根


Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史