题解

45 条题解

  • 0
    @ 2009-08-29 11:41:04

    题目描述啊

  • 0
    @ 2009-08-28 17:43:30

    出题人题目描述不厚道

    RP--

  • 0
    @ 2009-08-28 16:26:22

    郁闷,第一次,90,一模一样的程序,第二次95,第三次AC

    真是郁闷死了

    看来要学学nlogn的longestup的算法了,O(n^2)很容易超时啊!!!

  • 0
    @ 2009-08-28 14:33:51

    第一次交:

    编译通过...

    ├ 测试数据 01:答案正确... 822ms

    ├ 测试数据 02:答案正确... 853ms

    ├ 测试数据 03:答案正确... 838ms

    ├ 测试数据 04:答案正确... 838ms

    ├ 测试数据 05:运行超时...

    ├ 测试数据 06:答案正确... 181ms

    ├ 测试数据 07:答案正确... 166ms

    ├ 测试数据 08:答案正确... 197ms

    ├ 测试数据 09:答案正确... 212ms

    ├ 测试数据 10:答案正确... 181ms

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

    Unaccepted 有效得分:95 有效耗时:4288ms

    什么都没改,再交:

    编译通过...

    ├ 测试数据 01:答案正确... 838ms

    ├ 测试数据 02:答案正确... 822ms

    ├ 测试数据 03:答案正确... 806ms

    ├ 测试数据 04:答案正确... 822ms

    ├ 测试数据 05:答案正确... 822ms

    ├ 测试数据 06:答案正确... 166ms

    ├ 测试数据 07:答案正确... 166ms

    ├ 测试数据 08:答案正确... 134ms

    ├ 测试数据 09:答案正确... 150ms

    ├ 测试数据 10:答案正确... 166ms

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

    Accepted 有效得分:100 有效耗时:4892ms

    无语。。。。。。

  • 0
    @ 2009-08-28 00:07:58

    O(nlogn)

    用best[i]记录长度为i序列末尾的最小值

    易证best数组是不升的,可以二分求解

  • 0
    @ 2009-08-27 22:29:13

    编译通过...

    ├ 测试数据 01:答案正确... 697ms

    ├ 测试数据 02:答案正确... 681ms

    ├ 测试数据 03:答案正确... 697ms

    ├ 测试数据 04:答案正确... 712ms

    ├ 测试数据 05:答案正确... 681ms

    ├ 测试数据 06:答案正确... 119ms

    ├ 测试数据 07:答案正确... 119ms

    ├ 测试数据 08:答案正确... 119ms

    ├ 测试数据 09:答案正确... 134ms

    ├ 测试数据 10:答案正确... 119ms

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

    Accepted 有效得分:100 有效耗时:4078ms

    事实证明,数据弱,O(N^2)也能过。

    LX的题解很详细了 我就不多说了 就是一个由城市联谊变形过来的LongestUp

  • 0
    @ 2009-08-27 15:36:54

    看到十楼的话。一股智商上的优越感油然而生

  • 0
    @ 2009-08-27 15:27:27

    看懂题目花了半小时

    最后发现是经典问题!!!

    O(nlogn);

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-08-27 13:11:50

    O(N*N)的效果

    编译通过...

    ├ 测试数据 01:答案正确... 822ms

    ├ 测试数据 02:答案正确... 822ms

    ├ 测试数据 03:答案正确... 775ms

    ├ 测试数据 04:答案正确... 822ms

    ├ 测试数据 05:答案正确... 822ms

    ├ 测试数据 06:答案正确... 150ms

    ├ 测试数据 07:答案正确... 166ms

    ├ 测试数据 08:答案正确... 197ms

    ├ 测试数据 09:答案正确... 150ms

    ├ 测试数据 10:答案正确... 166ms

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

    Accepted 有效得分:100 有效耗时:4892ms

  • 0
    @ 2009-08-27 11:56:17

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    终于a了

  • 0
    @ 2009-08-27 11:27:08

    哎,快排打错了,0分

    -->[red]temp:=xc;xc:=xc[j,1];xc:=temp;

  • 0
    @ 2009-08-27 11:06:30

    单调队列的应用

  • 0
    @ 2009-08-27 10:59:18

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

    Flag   Accepted

    题号   P1638

    类型(?)   其它

    通过   34人

    提交   75次

    通过率   45%

    难度   0

  • 0
    @ 2009-08-27 10:18:28

    快排+DP+二分查找=0ms

  • 0
    @ 2009-08-27 10:15:14

    编译通过...

    ├ 测试数据 01:答案正确... 775ms

    ├ 测试数据 02:答案正确... 791ms

    ├ 测试数据 03:答案正确... 791ms

    ├ 测试数据 04:答案正确... 775ms

    ├ 测试数据 05:答案正确... 775ms

    ├ 测试数据 06:答案正确... 134ms

    ├ 测试数据 07:答案正确... 166ms

    ├ 测试数据 08:答案正确... 166ms

    ├ 测试数据 09:答案正确... 150ms

    ├ 测试数据 10:答案正确... 166ms

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

    Accepted 有效得分:100 有效耗时:4689ms

    惊险AC

  • 0
    @ 2009-08-27 09:29:17

    sgu原题~

  • 0
    @ 2009-08-27 08:50:16

    先快排。

    再用优化版的最长上升子序列。。。

    开个G数组记录F为1,2,3……时关键值最小的。。

    I 2 TO N

    J 从G数组DOWNTO 1

  • 0
    @ 2009-08-27 08:48:07

    明白了题意才知道

    这题目好水....

  • 0
    @ 2009-08-27 08:23:04

    要先排序,很简单的dp

    program exqjwj;

    var n,i,j,k,l,x,y,m1,m2:longint;

    b,d:array[1..500001,1..2]of qword;

    procedure kp(l,r:longint);

    var i,j,mid,k:longint;

    begin

    i:=l; j:=r; mid:=b[(l+r) div 2,1];

    repeat

    while bmid do dec(j);

    if ij;

    if ll) then

    begin

    l:=d[j,2];

    k:=j;

    end;

    if l>0 then

    begin

    d:=l+1;

    end;

    end;

    k:=1;

    for j:=1 to n do

    if d[j,2]>d[k,2] then k:=j;

    write(d[k,2]);

    readln;

    end.

  • 0
    @ 2009-08-27 08:07:16

    为什么我的程序算出来的答案都比正解大1?

    但是有一个数据又会大2……

    type

    City=record

    a,b:longint;

    end;

    var

    F:array[0..100000]of longint;

    c:array[0..100000]of City;

    n,m,i,j,ans,p,q,mid:longint;

    procedure qsort(l,r:longint);

    var

    i,j,mid:longint;

    swap:City;

    begin

    i:=l;j:=r;mid:=c[(i+j) shr 1].a;

    repeat

    while c[i].amid do dec(j);

    if ij;

    if iF[q] then

    begin

    if q=ans then inc(ans);

    F[q+1]:=c[i].b;

    end;

    if (c[i].b=F[q])and(q=ans) then inc(ans);

    if (c[i].bF[p]) then F[q]:=c[i].b;

    end;

    writeln(ans);

    end.

    谁帮忙看下 = =

信息

ID
1638
难度
6
分类
动态规划 | 动态规划 | LIS 点击显示
标签
(无)
递交数
752
已通过
226
通过率
30%
被复制
2
上传者