/ Vijos / 题库 / 导弹拦截 /

题解

203 条题解

  • 0
    @ 2007-08-24 11:41:11

    谁能提供一下专门讲这种动规的资料啊？先谢谢了。。

  • 0
    @ 2007-08-22 19:23:05

    编译通过...

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

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

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

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

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

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

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

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

  • 0
    @ 2007-08-12 20:54:42

    这一题理论上说dp+贪心是不对的，例如

    4 5 6 7 8 14 15 16 1 2 3 9 10 11 12 13

    若贪心：4 5 6 7 8 9 10 11 12 13

    14 15 16

    1 2 3

    要三组

    实际上：4 5 6 7 8 14 15 16

    1 2 3 9 10 11 12 13

    只要两组

  • 0
    @ 2007-08-05 23:55:46

    第二问用贪心能过吗？

    这个时代为什么还有人不用快排（楼下的牛犊）。。。

  • 0
    @ 2007-07-28 16:18:50

    "以后每一发炮弹都不能高于前一发的高度"??

    不能高于=小于？

    应该是不大于吧……

    害我的AC率又降了2个百分点

  • 0
    @ 2007-07-27 21:53:23

    DP+贪心的确是必过的。。

    可谁能告诉我，第2问用二分图匹配为什么会错3个点！！

  • 0
    @ 2008-11-02 10:33:48

    第一个问题用DP，第二可以用贪心法

  • 0
    @ 2007-06-21 20:47:05

    编译通过...

    ├ 测试数据 01：答案错误...

    　├ Hint: 注意观察样例数据　├ 标准行输出

    　├ 错误行输出

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

    ├ 测试数据 03：答案错误...

    　├ Hint: 注意考虑边界情况　├ 标准行输出

    　├ 错误行输出

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

    　├ 错误行输出

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

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

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

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

    汗..一半点多了1 一半点又没少1 晕倒..

    2次DP AC...还得-1..~

    编译通过...

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

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

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

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

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

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

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

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

  • 0
    @ 2007-06-01 09:38:06

    为什么第二问是最长递增子序列？？

    是高手发信息给我！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

    为什么第二问是最长递增子序列？？

    是高手发信息给我！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

    为什么第二问是最长递增子序列？？

    是高手发信息给我！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

    为什么第二问是最长递增子序列？？

    是高手发信息给我！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

  • 0
    @ 2007-05-20 17:12:57

    for(i=2;i=1;j--)

    if(a[j]>a[i] && opt[i]

  • 0
    @ 2007-05-19 18:37:13

    dp最长不上升字串。

    dp最长上升字串-1.

    此为正解！

    编译通过...

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

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

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

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

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

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

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

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

  • 0
    @ 2007-04-29 20:15:09

    From default

    导弹拦截 全国青少年信息学奥林匹克分区联赛 (NOIp) 竞赛原题

    编译通过...

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

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

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

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

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

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

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

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

    唉!!!!!!

    贪心算法:浙江大学出版的绿书上有.

  • 0
    @ 2007-03-09 15:13:36

    最后输出是sys-1,错了

  • 0
    @ 2007-03-28 16:51:45

    编译通过...

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

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

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

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

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

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

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

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

    二分+贪心=AC.

  • 0
    @ 2007-02-10 23:06:35

    编译通过...

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

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

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

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

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

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

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

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

    要求最少配备的系统数，就是求最长不上升序列的最小分划。

    我们可以证明它等于最长上升序列的长度，证明略。

    次句甚秒,可怎么证明?

  • 0
    @ 2007-01-02 22:26:59

    什么逻辑！！！！！第二问要减１！！！！

  • 0
    @ 2006-12-16 16:30:33

    有个偏序集的定理可证明.....................

  • 0
    @ 2006-12-15 22:49:05

    第二问是最长上升序列？？不敢相信，我用贪心的。

    数组记录最近一次打掉的导弹高度，来个导弹，用比它高的最低的一个打，如果没有比它高的就再增加一个系统。最后………………………………减1…………………………

  • 0
    @ 2006-12-01 20:50:31

    编译通过...

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

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

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

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

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

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

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

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

    ^0^

  • 0
    @ 2006-11-20 21:27:59

    不是吧?

    我第2问用贪心做啊,也是

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

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

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

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

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

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

    .

    从理论上讲,贪心绝对是没错的.用多次最长不降反而有问题了....而且每次贪心只是O(n)的..

导弹拦截

信息

ID
1303
难度
6
分类
动态规划 | 单调性DP 点击显示
标签
递交数
7594
已通过
2015
通过率
27%
被复制
12
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1