题解

22 条题解

  • 0
    @ 2013-08-30 11:02:25

    {
    丑陋的程序,丑陋的时间,好在比较短。。。
    }
    var
    f:array[0..100,0..100,1..3] of longint;
    a:array[1..100,1..3] of longint;
    i,j,k,n,m,ans,ii:longint;
    function max(x,y:longint):longint;
    begin
    if x>y then max:=x
    else max:=y;
    end;
    function c(x:longint):longint;
    begin
    if x=1 then c:=2;
    if x=2 then c:=3;
    if x=3 then c:=1;
    end;
    function d(x:longint):longint;
    begin
    d:=c(c(x));
    end;
    begin
    readln(n,m);
    for i:=1 to n do
    readln(a[i,1],a[i,2],a[i,3]);
    for i:=1 to n do
    for j:=1 to 3 do
    f[i,1,j]:=a[i,j];
    for i:=1 to n do
    for j:=1 to m do
    for k:=1 to 3 do
    begin
    for ii:=1 to i-1 do
    begin
    f[i,j,k]:=max(f[i,j,k],f[ii,j-1,1]+a[i,k]);
    f[i,j,k]:=max(f[i,j,k],f[ii,j-1,2]+a[i,k]);
    f[i,j,k]:=max(f[i,j,k],f[ii,j-1,3]+a[i,k]);
    if ((a[ii,1]>=a[i,c(k)])and(a[ii,2]>=a[i,d(k)]))or((a[ii,1]>=a[i,d(k)])and(a[ii,2]>=a[i,c(k)])) then
    f[i,j,k]:=max(f[i,j,k],f[ii,j,3]+a[i,k]);
    if ((a[ii,1]>=a[i,c(k)])and(a[ii,3]>=a[i,d(k)]))or((a[ii,1]>=a[i,d(k)])and(a[ii,3]>=a[i,c(k)])) then
    f[i,j,k]:=max(f[i,j,k],f[ii,j,2]+a[i,k]);
    if ((a[ii,3]>=a[i,c(k)])and(a[ii,2]>=a[i,d(k)]))or((a[ii,3]>=a[i,d(k)])and(a[ii,2]>=a[i,c(k)])) then
    f[i,j,k]:=max(f[i,j,k],f[ii,j,1]+a[i,k]);
    end;
    ans:=max(ans,f[i,j,k]);
    end;
    writeln(ans);
    end.

  • 0
    @ 2010-07-07 11:55:57

    var n,m:Longint;

      a,b,c:array[0..100] of longint;

      bl:array[0..100,0..3] of longint;

      f:array[0..100,0..100,0..3] of longint;

    procedure init;

    var i:longint;

    begin

       readln(n,m);

       a[0]:=0;b[0]:=0;c[0]:=0;fillchar(bl,sizeof(bl),0);

       for i:=1 to n do

         begin

           readln(a[i],b[i],c[i]);

           block:=c[i];

           block:=a[i];

           block:=b[i];

         end;

    end;

    function max(a,b:longint):longint;

    begin

       if a=x2)and(y1>=y2))or((x1>=y2)and(y1>=x2)) then exit(true) else exit(false);

    end;

    procedure find;

    var i,j,t,k,p,h:longint;

    begin

       f[1,1,1]:=bl[1,1];f[1,1,2]:=bl[1,2];f[1,1,3]:=bl[1,3];

       for i:=2 to n do

         for p:=1 to i-1 do

           for j:=1 to i do

             for k:=1 to 3 do

               for h:=1 to 3 do

                 begin

                   if ok(p,h,i,k) then

                     begin

                       f:=max(f[p,j,h]+bl,f);

                       t:=f;

                     end;

                   f:=max(f[p,j-1,h]+bl,f);

                   t:=f;

                 end;

       t:=0;

       for i:=m to n do

         for j:=1 to 3 do t:=max(t,f);

       writeln(t);

    end;

    begin

       init;

       find;

    end.

  • 0
    @ 2009-11-09 11:54:01

    DP

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

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var n,m:Longint;

    a,b,c:array[0..100]of longint;

    block:array[0..100,0..3]of longint;

    f:array[0..100,0..100,0..3]of longint;

    procedure init;

    var i:longint;

    begin

    readln(n,m);

    a[0]:=0;b[0]:=0;c[0]:=0;fillchar(block,sizeof(block),0);

    for i:=1 to n do

    begin

    readln(a[i],b[i],c[i]);

    block:=c[i];

    block:=a[i];

    block:=b[i];

    end;

    end;

    function max(a,b:longint):longint;

    begin

    if a=x2)and(y1>=y2))or((x1>=y2)and(y1>=x2)) then exit(true) else exit(false);

    end;

    procedure find;

    var i,j,t,k,p,h:longint;

    begin

    fillchar(f,sizeof(f),0);

    {for i:=1 to m do

    for k:=1 to 3 do

    for p:=1 to 3 do

    f:=max(f,f+block);

    }

    f[1,1,1]:=block[1,1];f[1,1,2]:=block[1,2];f[1,1,3]:=block[1,3];

    for i:=2 to n do

    for p:=1 to i-1 do

    for j:=1 to i do

    for k:=1 to 3 do

    for h:=1 to 3 do

    begin

    if ok(p,h,i,k) then

    begin

    f:=max(f[p,j,h]+block,f);

    t:=f;

    end;

    f:=max(f[p,j-1,h]+block,f);

    t:=f;

    end;

    t:=0;

    for i:=m to n do

    for j:=1 to 3 do t:=max(t,f);

    writeln(t);

    end;

    begin

    init;

    find;

    end.

    Flag    Accepted

    题号   P1464

    类型(?)   动态规划

    通过   52人

    提交   125次

    通过率   42%

    难度   2

    提交 讨论 题解

  • 0
    @ 2009-10-28 20:50:39

    判边长少写了个等号,悲惨地多交了三次呀...

  • 0
    @ 2009-10-24 17:02:48

    这也忒牛了,这哪是97年的题啊...

  • 0
    @ 2009-10-22 22:38:41

    本题是最近才添加的

    97年NOI第二试试题的说

    分类放错地方的说

    本题的解法可以参考lrj的黑书P119

  • 0
    @ 2009-10-19 21:38:36

    新题目,诧异了,为什么现在才发现?

    1次AC,爽~~

  • 0
    @ 2009-10-14 22:10:12

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    这不是NOIp97的题目吧?

  • 0
    @ 2009-10-11 09:39:20

    dpdpdpdpdpdpdpdpdpdpdddp!!!!!!

  • 0
    @ 2009-10-10 19:47:46

    好隐蔽的题目

  • 0
    @ 2009-10-08 21:01:56

    bs楼下,粘代码……

    一次AC 哈哈 爽!!

    双重DP,O(n^3+n*n*m)

  • 0
    @ 2009-10-08 19:49:19

    我擦- -一个疏忽让我没能一次AC。。。

    注意最后打的是全部dp数组里的最大值- -

    不是dp【m,n,k】(k=1..3)的最大值。。。。

    方程好写---|

    if (f[j,t,k,kk]) then

    dp[j,i,k]:=max(dp[j,i,k],max(dp[t,i-1,kk],dp[t,i,kk])+a[j,k])

    else

    dp[j,i,k]:=max(dp[j,i,k],dp[t,i-1,kk]+a[j,k]);

    难写的是比较上一个能不能包含此个的那段代码。。。

    var

    ans,m,n,ka,kb,kka,kkb,j,i,k,kk,t:longint;

    f:array[0..100,0..100,1..3,1..3]of boolean;

    a:array[0..100,1..3]of longint;

    dp:array[0..100,0..100,1..3]of longint;

    function max(p,g:longint):longint;

    begin

    if p>g then exit(p) else exit(g);

    end;

    begin

    read(m,n);

    for i:=1 to m do

    begin

    for j:=1 to 3 do

    read(a);

    end;

    for j:=2 to m do

    for t:=1 to j-1 do

    for k:=1 to 3 do

    for kk:=1 to 3 do

    begin

    case k of

    1:begin ka:=a[j,2]; kb:=a[j,3]; end;

    2:begin ka:=a[j,1]; kb:=a[j,3]; end;

    3:begin ka:=a[j,1]; kb:=a[j,2]; end;

    end;

    case kk of

    1:begin kka:=a[t,2]; kkb:=a[t,3]; end;

    2:begin kka:=a[t,1]; kkb:=a[t,3]; end;

    3:begin kka:=a[t,1]; kkb:=a[t,2]; end;

    end;

    if (((ka

  • 0
    @ 2009-10-07 18:57:50

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

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

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

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

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

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

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

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

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

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

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

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

    弱弱的DP.. 88ms..

  • 0
    @ 2009-10-07 14:41:28

    犯低级错误了~~~

  • 0
    @ 2009-10-07 10:53:25

    蛮简单的一道DP

    F

    表示前I跟柱子分成J组,最后一跟柱子是以第I跟柱子以第K条边做高的最大值

    F:=MAX(F[1..I-1,J-1,1..3],F[1..I-1,J,1..3](a

  • 0
    @ 2008-11-05 18:16:15

    怎么还不通过??

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

    地板

  • 0
    @ 2008-10-13 14:01:16

    抢不过你们~~

  • 0
    @ 2008-10-07 22:20:00

    hehe

  • 0
    @ 2008-10-06 13:43:44

    Orz= =

    bandeng

信息

ID
1464
难度
5
分类
动态规划 点击显示
标签
递交数
501
已通过
182
通过率
36%
被复制
4
上传者