• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1010 – STAMPS

    ACM-POJ EXP 224阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    题意比较难懂。大致如下:

    第一行数字是邮票的面值,每一个数字就是一个不同的种类,哪怕面值相同。以0结束。

    第二行数字是顾客所需要的邮票总面值。每个数字就是一个顾客的需求,以0结束。

    每两行是一组case。以EOF结束输入。

    顾客是集邮爱好者,所以你必须尽可能的给他不同种类的邮票。

    但是一位顾客最多只能拿4张邮票。

    显然,我们拥有的邮票就是第一行中的数据。

    解题思路

    DFS寻找所有的解,再逐一比较寻找最优解,剪枝是关键。

    关于tie。

    满足顾客需求的解就是可行解。

    邮票种类最多的可行解为最优。

    如果存在两个以上的最优解的邮票种类是一样的,张数最少的更优

    张数也一样的话,这些最优解中最大面值较大的更优。

    若邮票种类、张数、最大面值三者都分别相同,则认为这些最优解相同,输出tie。

    没有解就是none。


    做法大致有三种

    1、枚举。反正最多拿4张,可以4重循环暴搜最优解。

    2、DFS。每次搜索后,如果有解,更新最优解,关键在剪枝。

    3、三维DP。这个没怎么研究,不太懂……


    我用的是第二种DFS

    剪枝

    1、最多拿四张邮票,如果同一面值的邮票种类超过5,以5计算。

    为什么不以4计算呢?因为tie

    2、若DFS的深度超过了4,那么就返回。(最多四张邮票)

    3、技巧剪枝:

    先对输入的邮票按面值升序排序,DFS到面值k时,不再搜索面值<k的邮票。

    同时排序也是为了保证DFS的最优解的邮票种类最多。

    Source修正

    Pacific Northwest 1998

    测试数据

    本文第二页附带测试数据

    测试数据下载

    转载请注明:EXP 技术分享博客 » POJ1010 – STAMPS

    喜欢 (1) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址