/ Vijos / 题库 / 合唱队形 /

题解

304 条题解

  • 0
    @ 2007-03-21 16:51:14

    二分效率O(n*log2^n),DP效率O(n^2),差别也太大了吧？？？

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

    从左向右,再从右向左各进行一次最长不XX序列,然后算出最大可以容纳人数,再用总人数减去就OK:)

  • 0
    @ 2007-01-02 12:39:45

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2006-11-14 17:00:39

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    相等的不能取考～～～～

  • 0
    @ 2006-11-13 19:13:00

    a[i]存第i个人的身高

    b[i]存以第i个人为终点的最长上升序列元素个数

    b[i]=max{b[j]|a[i]>a[j]&1

  • 0
    @ 2006-11-11 20:46:42

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    n-最长不降子序列与最长不升子序列只和最大者+1即是解

  • 0
    @ 2006-11-10 20:44:04

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2006-11-04 09:05:21

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

    　├ 错误行输出

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

    　├ 错误行输出

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

    　├ 错误行输出

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

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

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

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

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

    　├ 错误行输出

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

    　├ 错误行输出

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

    错误答案总是跟正确答案差１，怎么回事？

  • 0
    @ 2006-10-26 11:55:35

    最长不降子序列 O(n^2logn)

  • 0
    @ 2006-10-23 20:27:32

    交了3次

    错在最长下降序列的生成上 f2[i]应该表示i-n的最长下降序列 而不是1-i的

  • 0
    @ 2006-10-12 16:31:06

    两边求递增序列，然后求max。easy!

  • 0
    @ 2006-10-11 20:23:07

    很搞笑的一个失误：

    for i:=1 to n do

    if b[i]+c[i]+1>max then max:=i;{应该是max:=b[i]+c[i]+1}

    writeln(n-b[max]-c[max]-1);

    这样也可以过5个数据……

  • 0
    @ 2006-10-08 17:40:42

    动态规划

    数组 a→记录高度 b[i]→到第i个人能排列最多的人数

    对i个人进行枚举:

    假设以i为最高，将数据分为(1..i)和(i..n)，分别动态规划。动态规划时先用1循环J（表示到J时的最大人数），里面再套个循环K计算到J的最大人数，同时不断跟新b[j]，记录下最大人数。动态规划后，将最大数汇总。

    PS：大家想找这题有关的资料，可以上网找找里的'最长不下降序列'。

  • 0
    @ 2006-10-05 14:32:38

    以前能很快解决这道题目。。。。

    很奇怪现在不行了

  • 0
    @ 2006-10-04 22:42:40

    注意是:n-k,我错了N次

  • 0
    @ 2006-08-21 15:54:28

    f[i]表示从左到右最长上升子序列长度，

    g[i]表示从左到右最长下降子序列长度。

    tem:=max{ f[k]+max{g[k+1..n+1]} }

    最后解为 n-tem

  • 0
    @ 2006-08-13 17:38:28

    数据规模不大啊,直接枚举最高点就行了

  • 0
    @ 2006-07-27 23:28:23

    DP基础题....最长不降/最长不升

  • 0
    @ 2006-06-05 14:47:48

    两次DP，找左边最长上升和右边最长上升，再找最高点

    做的第一道DP题，纪念一下

  • 0
    @ 2006-06-02 20:41:04

    偶用两次DP～～

    一次左到右的最长上升序列+一次右到左的最长上升序列+枚举最高点

合唱队形

信息

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