/ Vijos / 题库 / 岳麓山上打水 /

题解

53 条题解

  • 0
    @ 2009-08-13 20:13:47

    whyvine的解题报告：

    http://blog.sina.com.cn/s/blog_618b6ea70100egn0.html

  • 0
    @ 2009-08-10 20:26:37

    这道题想了一天，没想到什么办法，只好用搜索，竟然AC了～～囧，数据太弱了～～

  • 0
    @ 2009-08-07 18:01:21

    快排呀快排呀其实没什么关系

    检查时：1个数直接mod

    2个数用最大公约数检验一下再dp

    3个数...

  • 0
    @ 2009-08-03 22:34:08

    dfsid。做DP的时候用队列来做，比较快。

    而且，最重要的是，一定要排序！而且一定要用快排！切记切记！一定要用快排！

  • 0
    @ 2009-07-12 20:22:17

    怎么做

  • 0
    @ 2009-06-22 12:06:49

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 165ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 462ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：627ms

    我恨 Vag 6K

  • 0
    @ 2009-05-26 08:16:05

    DFS+ID+无限背包判断。

  • 0
    @ 2009-05-03 20:34:14

    迭代加深搜索枚举最小数目以及哪些包，然后用完全背包问题加以构造来验证是否可行。

    注意到在验证时，由于每个包都要用到，所以并非初始状态并非f[0]=true.而应该是f[Σ（已经选了的物品容积）]=true.这是一个效果明显的优化。

  • 0
    @ 2009-04-01 20:31:11

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 103ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 212ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：315ms

    USACO 最后一点0.8s。。。

  • 0
    @ 2008-11-09 18:57:27

    80-80-90-40-100 - -

    前3次都超时，第4次把一个局部数组定义成了全局数组，囧。

    方法还是前辈们用的DFSID+DP

    得出一种组合后再O（PQ）的DP要超时

    优化是每次加入一个桶后立即做一次O（Q）的DP

    答案最多是3种桶，估计如果数据刁一点，这种方法肯定是不行的

    直接做DP可以拿90分，但是方法原理是有后效性的，拿90是运气（OR 数据弱？）

    大牛的方法是：先求出组成体积为K所需最小的桶种数，然后在Q的约数中找一个所需桶种数最小的（对于q的任意一个约数q[k]（包括1和它本身），若有一种生成的数的集合能凑出q[k]，则以这些数一定能凑出Q）。然后再一遍DFS。

    这个算法原理就是先算出最少需要桶种类数，再找出这些桶是哪些。

  • 0
    @ 2008-11-06 10:15:38

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案错误...　├ 标准行输出

    　├ 错误行输出

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分：90 有效耗时：0ms

    疯了....

  • 0
    @ 2008-11-01 14:28:15

    DFSID+DP

  • 0
    @ 2008-10-23 16:17:53

    数据要先冒一下泡……

  • 0
    @ 2008-10-21 21:10:55

    为什么我就是70分 始终过不了啊 郁闷 楼下哪位大牛介绍下保存方案的方法啊 谢谢了 我感觉写得异常复杂 55555555555

  • 0
    @ 2008-10-21 17:19:39

    等一串WAITING．．．．等了２小时　最后上来看看　ＡＣ了　．．．．

  • 0
    @ 2009-06-27 21:10:26

    爽啊,一遍ac. dfs-id又好写又快.估计再加俩剪枝就秒杀了.没难度3,大家放心做.

    题解 http://freepascal.spaces.live.com/blog/cns!34840F274352AFEC!145.entry

  • 0
    @ 2008-10-07 23:23:09

    无限背包+判断并记录最小路径可AC

  • 0
    @ 2008-09-11 17:57:43

    我首先用无限背包做，只得７０，不知是否这样能ac．

  • 0
    @ 2008-08-13 22:01:24

    DFSID+DP真经典。

    首先，由于同的个数不确定，搜索的使用迭代加深搜索，不断加深个数，搜索。每得到一个方案，用简单的01背包判断是否合法，合法直 接退出。由于字典序要最小，先qsort一遍。再加上vivid puppy就可以ac了。

    （我才发现我是第100个）：）

  • 0
    @ 2008-08-11 20:24:21

    USACO-5.3.1 milk searching原题，只改变了输出方式，不懂的可以百度找

    USACO milk searching题解，肯定能找到

岳麓山上打水

信息

ID
1159
难度
7
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
2012
已通过
457
通过率
23%
被复制
5
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1