题解

126 条题解

  • 0
    @ 2009-09-04 20:16:26

    区间DP。。

    求最值很简单~

    输出算式要写得优美就很考功力了~

    每个区间内递归求算式时,切割区间的变量要从上界到下界循环,即

    for i:=R downto L do

  • 0
    @ 2009-09-04 16:16:10

    编译通过...

    ├ 测试数据 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-09-04 15:22:38

    .....楼下的应该不是冯一大牛吧..........

  • 0
    @ 2009-09-04 14:49:36

    vijos 封号的SB

  • 0
    @ 2009-09-02 21:10:26

    编译通过...

    ├ 测试数据 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-09-02 20:55:35

    晕,我忘了考虑多解怎样输出了………………要改成'

  • 0
    @ 2009-08-29 18:45:05

    感谢楼上某牛的数据 >

  • 0
    @ 2009-08-28 23:54:31

    PRE记录F这个状态的分割点是第几个、

    然后DFS

  • 0
    @ 2009-08-26 11:24:37

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:运行超时|格式错误...

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

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

    请问一下第八个数据是什么

    。。

    又交了遍 没有改动 居然过了

  • 0
    @ 2009-08-25 09:26:02

    Orz fenghao

  • 0
    @ 2009-08-20 21:50:14

    区间dp+记录节点

    然后根据节点输出

    多解时括号尽量向前,即尽量在后面更新解

    一次AC...

  • 0
    @ 2009-08-19 18:31:40

    说实话。。

    题目挺好的。。

    不过出题人总得把多解输出给说清楚吧。。

    下面说说做法:

    转移方程:

    f=min{f+f[k+1,j]}+sum

    f表示从i到j的最小中间和

    g表示取得最小中间和的断点(这里补充一下,多解时候把括号尽量向前输出,所以只要最小中间和相等的也要更新g):

    function dp(l,r:longint):longint;

    var k,t:longint;

    begin

    if f[l,r]max then exit(f[l,r]);

    for k:=l to r-1 do

    begin

    t:=dp(l,k)+dp(k+1,r);

    if t

  • 0
    @ 2009-08-17 21:57:41

    沙茶のdp

    变态の输出

    用kh表示第i个数前的左括号数

    kh表示第i个数后的右括号数

    每处理一个区间[x,y]只要inc(kh[x,0]); inc(kh[y,1]);

    输出时处理即可

  • 0
    @ 2009-08-14 09:07:40

    编译通过...

    ├ 测试数据 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-13 22:09:09

    石子合并动归

    注意括号尽量向前,向前!

  • 0
    @ 2009-08-12 17:25:52

    终于AC了……BS出题人,为啥不说明多解要括号放前面?!

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    为啥我只有80分?

    多解怎么提前啊?

    编译通过...

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

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

     ├ 错误行输出

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

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

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

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

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

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

     ├ 错误行输出

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

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

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

    Unaccepted 有效得分:80 有效耗时:0ms

  • 0
    @ 2009-08-12 14:33:16

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    注意, 多解的情况括号尽量向前. 否则只有80分...

    BS出题人.

  • 0
    @ 2009-08-12 10:53:42

    var

    n,min,p,i,j,l,k,t:longint;

    a,sum:array[0..50] of longint;

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

    cut:array[0..100,0..100] of longint;

    procedure deal(i,j:longint);

    begin

    if i>=j then exit;

    deal(i,cut);

    deal(cut+1,j);

    write(sum[j]-sum,' ');

    end;

    procedure output(i,j:longint);

    begin

    if i>=j then

    begin

    write(a[i]);

    exit;

    end;

    write('(');

    output(i,cut);

    write('+');

    output(cut+1,j);

    write(')');

    end;

    begin

    assign(input,'a2.in');

    reset(input);

    readln(n);

    for i:=1 to n do

    read(a[i]);

    for i:=1 to n do

    begin

    sum[i]:=sum+a[i];

    f:=0;

    cut:=i;

    end;

    for l:=2 to n do

    for i:=1 to n-l+1 do

    begin

    j:=i+l-1;

    min:=maxlongint;

    for k:=i to j-1 do

    if f+f[k+1,j]

  • 0
    @ 2009-08-12 10:27:46

    强烈tanconghui

    他的数据有误

    给几个数据吧

    1:

    5

    5 2 4 1 3

    输出

    ((5+2)+(4+(1+3)))

    34

    7 4 8 15

    2:3

    2 2 2

    输出

    ((2+2)+2)

    10

    4 6

    3:

    8

    1 1 2 2 3 4 6 9

    输出

    (((((1+1)+2)+2)+(3+4))+(6+9))

    75

    2 4 6 7 13 15 28

    动归应该很平常

    就不讲了吧

  • 0
    @ 2009-08-10 18:16:30

    如对本题有疑问可以参看我的题解:http://xujieqi.blog.hexun.com/36057609_d.html

信息

ID
1038
难度
5
分类
动态规划 点击显示
标签
(无)
递交数
2724
已通过
1011
通过率
37%
被复制
10
上传者