题解

145 条题解

  • 0
    @ 2014-01-07 16:18:04

    const maxn=30;
    var i,j,n,d:longint;
    ans:longint;
    a:array[1..maxn] of longint;
    value:array[1..maxn,1..maxn] of comp;
    root:array[1..maxn,1..maxn] of longint;
    s,temp:comp;
    f1,f2:text;
    fn1,fn2,fileno:string;
    procedure preorder(p1,p2:longint);
    begin
    if p2>=p1 then begin
    inc(ans);
    if ans=n then write(root[p1,p2]) else
    write(root[p1,p2],' ');
    preorder(p1,root[p1,p2]-1);
    preorder(root[p1,p2]+1,p2);
    end;
    end;
    begin
    //readln(fileno);
    readln(n);
    for i:=1 to n do
    read(a[i]);
    fillchar(value,sizeof(value),0);
    for i:=1 to n do
    begin
    value[i,i]:=a[i];
    root[i,i]:=i;
    end;
    for i:=1 to n do
    begin
    value[i,i+1]:=a[i]+a[i+1];
    root[i,i+1]:=i;
    end;
    for d:=2 to n-1 do
    begin
    for i:=1 to n-d do
    begin
    s:=value[i,i]+value[i+1,i+d];
    root[i,i+d]:=i;
    for j:=1 to d do
    begin
    temp:=value[i+j,i+j]+value[i,i+j-1]*value[i+j+1,i+d];
    if temp>s then begin
    s:=temp;
    root[i,i+d]:=i+j;
    end;
    end;
    temp:=value[i,i+d-1]+value[i+d,i+d];
    if temp>s then begin
    s:=temp;
    root[i,i+d]:=i+d+1;
    end;
    value[i,i+d]:=s;
    end;
    end;
    writeln(value[1,n]:0:0);
    preorder(1,n);
    end.

  • 0
    @ 2013-10-29 18:48:01

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 536 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 540 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 544 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 20
    测试数据 #4: Accepted, time = 0 ms, mem = 540 KiB, score = 20
    Accepted, time = 0 ms, mem = 544 KiB, score = 100
    代码
    #include<cstdio>
    #include<algorithm>
    int n,v[31],g[31][31];
    int s(int l,int r) {
    if (g[l][r]) return g[l][r];
    for(int i=l;i<=r;i++)g[l][r]=std::max(g[l][r],s(l,i-1)*s(i+1,r)+v[i]);
    return g[l][r];
    }
    void p(int l,int r) {
    if (l>r) return; else if (l==r) {printf("%d ",l); return; }
    int i=1; while (g[l][i-1]*g[i+1][r]+v[i]!=g[l][r]) i++;
    printf("%d ",i); p(l,i-1); p(i+1,r);
    }
    int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&v[i]);
    for (int i=1; i<=n; i++) g[ i ][ i ]=v[i] ;
    for (int i=1; i<=n; i++)
    for (int j=0; j< i; j++) g[ i ][ j ]= 1 ;
    printf("%d\n",s(1,n)); p(1,n);
    }

  • 0
    @ 2013-09-02 19:52:13

    #include <cstdio>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    #define MAXN 50

    long long f[MAXN][MAXN];
    bool flag[MAXN][MAXN];

    int a[MAXN];
    int n;

    int d[MAXN][MAXN];

    long long dp(int l,int r){
    if (l>r){
    return 1;
    }
    if (flag[l][r]){
    return f[l][r];
    }
    if (l==r){
    f[l][r]=a[l];
    flag[l][r]=true;
    return f[l][r];
    }
    f[l][r]=0;
    for (int i=l;i<=r;i++){
    long long rec=dp(l,i-1)*dp(i+1,r)+a[i];
    if (rec>f[l][r]){
    f[l][r]=rec;
    d[l][r]=i;
    }
    }
    flag[l][r]=true;
    return f[l][r];
    }

    void putans(int l,int r){
    if (l>r){
    return ;
    }
    if (l==r){
    printf("%d ",l);
    return ;
    }
    printf("%d ",d[l][r]);
    putans(l,d[l][r]-1);
    putans(d[l][r]+1,r);
    }

    int main(){
    scanf("%d",&n);
    for (int i=0;i++<n;){
    scanf("%d",&a[i]);
    }
    memset(flag,false,sizeof(flag));
    printf("%lld\n",dp(1,n));
    putans(1,n);
    return 0;
    }

  • 0
    @ 2013-08-15 10:57:10

    var
    i,j,k,n : longint;
    a : array[1..30] of longint;
    f : array[1..30,0..30] of longint;
    rt : array[1..30,0..30] of longint;

    procedure print(l,r:longint);
    var y : longint;
    begin
    if rt[l,r]<>0 then
    begin
    y := rt[l,r];
    write(y,' ');
    print(l,y-1);
    print(y+1,r);
    end;
    end;

    begin
    readln(n);
    for i := 1 to n do
    begin
    read(a[i]);
    f[i,i] := a[i];
    f[i,i-1] := 1; rt[i,i] := i;
    end;
    for i := 1 to n-1 do
    for j := 1 to n-i do
    for k := j to j+i do
    if f[j,j+i]<f[j,k-1]*f[k+1,j+i]+a[k] then
    begin
    rt[j,j+i] := k;
    f[j,j+i] := f[j,k-1]*f[k+1,j+i]+a[k];
    end;
    writeln(f[1,n]);
    print(1,n);
    end.

  • 0
    @ 2013-08-13 21:35:37

    ###block code
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define maxn 30

    using namespace std;

    int a[maxn+1],f[maxn+1][maxn+1];

    void digui(int w,int l,int r)
    {
    int i;
    if(l>=r){ if(l==r)printf("%d ",l); return ;}
    for(i=l;i<=r;i++)
    if(f[l][i-1]*f[i+1][r]+a[i]==w)break;
    printf("%d ",i);
    digui(f[l][i-1],l,i-1);
    digui(f[i+1][r],i+1,r);
    }

    int main()
    {
    int i,j,k,t,y,n,l,maxx;
    while(~scanf("%d",&n))
    {
    for(i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    f[i][i-1]=1;
    f[i][i]=a[i];
    }
    for(l=2;l<=n;l++)
    {
    for(i=1;i<=n-l+1;i++)
    {
    j=i+l-1;
    maxx=0;
    for(k=i;k<=j;k++)
    if(maxx<f[i][k-1]*f[k+1][j]+a[k])maxx=f[i][k-1]*f[k+1][j]+a[k];
    f[i][j]=maxx;
    }
    }
    printf("%d\n",f[1][n]);
    digui(f[1][n],1,n);
    printf("\n");
    }
    return 0;
    }

  • 0
    @ 2013-07-21 16:06:11

    水水的..

    var
    i,j,k,n : longint;
    a : array[1..30] of longint;
    f : array[1..30,0..30] of longint;
    rt : array[1..30,0..30] of longint;

    procedure print(l,r : longint);
    var y : longint;
    begin
    if rt[l,r]<>0 then
    begin
    y := rt[l,r];
    write(y,' ');
    print(l,y-1);
    print(y+1,r);
    end;
    end;

    begin
    readln(n);
    for i := 1 to n do
    begin
    read(a[i]);
    f[i,i] := a[i];
    f[i,0] := 1; f[i,i-1] := 1; rt[i,i] := i;
    end;
    for i := 1 to n-1 do
    for j := 1 to n-i do
    for k := j to j+i do
    if f[j,j+i]<f[j,k-1]*f[k+1,j+i]+a[k] then
    begin
    rt[j,j+i] := k;
    f[j,j+i] := f[j,k-1]*f[k+1,j+i]+a[k];
    end;
    writeln(f[1,n]);
    print(1,n);
    end.

  • 0
    @ 2013-02-26 23:29:13

    区间DP加递归输出路径,和石子合并差不多,W了3次后过了,注意要开INT64,C,V,B,D不要打错就行了
    var c,v,b,t,d,l,i,j,n,k:longint;
    ans:int64;
    a,w:array[1..30]of longint;
    f:array[1..30,1..30]of int64;
    g:array[1..30,1..30]of longint;
    procedure dg(c,v,b,d:longint);
    begin
    if v-c>1 then
    begin t:=t+1;w[t]:=g[c,v];dg(c,g[c,v]-1,g[c,v]+1,v)end
    else begin
    for i:=c to v do begin
    t:=t+1;
    w[t]:=i;
    end
    end;
    if d-b>1 then
    begin t:=t+1;w[t]:=g[b,d];dg(b,g[b,d]-1,g[b,d]+1,d)end
    else begin
    for i:=b to d do begin
    inc(t);
    w[t]:=i;
    end;
    end;
    end;
    function max(a,b:int64):int64;
    begin
    if a>b then exit(a)
    else exit(b);
    end;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);
    if n=1 then begin
    writeln(a[1]);
    writeln('1');
    exit;
    end;
    for i:=1 to n-1 do begin
    f[i,i+1]:=a[i]+a[i+1];
    f[i,i]:=a[i];
    end;
    f[n,n]:=a[n];
    for l:=3 to n do
    for i:=1 to n-l+1 do begin
    j:=i+l-1;
    ans:=-1;
    for k:=i to j do begin
    if k=i then f[i,j]:=max(f[i,j],a[k]+f[k+1,j])
    else if k=j then
    f[i,j]:=max(f[i,j],a[k]+f[i,k-1])
    else f[i,j]:=max(f[i,j],a[k]+f[i,k-1]*f[k+1,j]);
    if f[i,j]>ans then begin
    ans:=f[i,j];
    g[i,j]:=k;
    end;
    end;
    end;
    writeln(f[1,n]);
    c:=1;v:=g[1,n]-1;b:=g[1,n]+1;d:=n;
    dg(c,v,b,d);
    if n>2 then begin
    write(g[1,n]);
    for i:=1 to t do write(' ',w[i]);writeln;
    end
    else begin
    write(w[1]);
    for i:=2 to t do write(' ',w[i]);writeln;
    end;
    end.

  • 0
    @ 2010-07-06 17:38:45

    字典序搞了很久,求值 并不难

    var

    n,be,L,i,j:longint;

    score:Array[1..30] of longint;

    f:Array[0..31,0..31] of int64;

    ans:int64;

    function max(x,y:int64):int64;

    begin

    if x

  • 0
    @ 2010-04-14 20:35:17

    program addtro;

    var

    a:array[1..30]of int64;

    f,r:array[1..30,1..30]of int64;

    i,j,k,n,m:longint;

    procedure print(i,j:longint);

    begin

    if i>j then exit;

    write(' ',r);

    if i=j then exit;

    print(i,r-1);

    print(r+1,j);

    end;

    begin

    readln(n);

    for i:=1 to n do

    read(a[i]);

    for i:=1 to n do

    begin f:=a[i];r:=i;end;

    for k:=1 to n do

    for i:=1 to n-k do

    begin

    if f+f>=f+fthen

    begin f:=f+f;r:=i;end else

    begin f:=f+f;r:=i+k end;

    for j:=i+1 to i+k-1 do

    if f*f[j+1,i+k]+f[j,j]>f then begin f:=f*f[j+1,i+k]+f[j,j];r:=j;end;

    end;

    writeln(f[1,n]);

    write(r[1,n]);

    print(1,r[1,n]-1);

    print(r[1,n]+1,n);

    end.

    就是第二问………………………………………………………………邪恶

  • 0
    @ 2010-03-11 19:00:56

    第二问太邪恶了。。

    非要字典序输出..

  • 0
    @ 2009-11-08 22:47:24

    交了4次 虽然0msA了 但是还有两个问题

    1、当一颗子树只有两个节点的时候 谁做根都是一样的啊。。害我为了wa改了半天

    2、输出遍历的时候怎么是两个空格隔开?第一个数字前还要空格 什么啊,跟样例完全不一样

  • 0
    @ 2009-11-06 09:43:33

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

  • 0
    @ 2009-11-02 20:30:14

    编译通过...

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

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

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

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

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

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

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

    感慨啊~!交了三次,这么水的题居然要交三次……

    原因很简单,第一次我初始化时没有考虑f[i][0]情况;

    第二次在转移时打了

  • 0
    @ 2009-10-31 19:07:06

    program lq;

    const

    inf='binary.in';

    ouf='binary.out';

    var

    n,i,j,k :longint;

    max,l,r :qword;

    a :array[0..30] of qword;

    f,s :array[0..30,0..30] of qword;

    procedure change(l,r:longint);

    begin

    if l>r then exit;

    if l=r then begin //particularly situation,prevent 215

    write(l,' ');

    exit

    end;

    write(s[l,r],' '); //l>0,r>0.

    change(l,s[l,r]-1);

    change(s[l,r]+1,r);

    end;

    //[lq]

    begin

    //int

    readln(n);

    for i:=1 to n do

    read(a[i]);

    //start

    for i:=1 to n do

    f:=a[i];

    //main---|DP

    for i:=n downto 1 do

    for j:=i+1 to n do

    for k:=i to j do begin

    if i>k-1 then l:=1 else l:=f;

    if k+1>j then r:=1 else r:=f[k+1,j];

    if f

  • 0
    @ 2009-10-30 12:23:20

    type

    arr=record

    da:longint;

    mid:longint;

    end;

    var

    t,k,i,n,j,re,m,p:longint;

    d:array [1..30] of longint;

    f:array [0..30,0..30] of arr;

    procedure print(l,r:longint);

    begin

    if l

  • 0
    @ 2009-10-27 19:37:37

    各位大牛帮我看看吧,为什么最后一个点超时了~`\

    = =~``

    var a:array[1..21,0..20]of longint;

    a1:array[1..21,0..20]of string;

    b:array[1..20]of integer;

    c,i,j,k,n:longint;

    begin

    readln(n);

    for i:=1 to n do

    read(b[i]);

    readln;

    c:=0;

    for i:=1 to n do

    begin

    a:=b[i];

    j:=i;

    while j0 do

    begin

    a1:=chr(j mod 10+48)+a1;

    j:=j div 10;

    end;

    end;

    for i:=1 to n do

    begin

    a:=1;

    a1:='';

    end;

    for i:=n-1 downto 1 do

    for j:=i+1 to n do

    for k:=i-1 to j-1 do

    if a*a[k+2,j]+a[k+1,k+1]>a then

    begin

    a:=a*a[k+2,j]+a[k+1,k+1];

    a1:=a1[k+1,k+1]+' '+a1+' '+a1[k+2,j];

    end;

    writeln(a[1,n]);

    j:=0;

    for i:=1 to length(a1[1,n]) do

    begin

    if (a1[1,n][i]=' ')and(j0) then

    begin

    write(a1[1,n][i]);

    j:=0;

    end;

    if a1[1,n][i]' ' then

    begin

    write(a1[1,n][i]);

    j:=1;

    end;

    end;

    end.

  • 0
    @ 2009-10-26 17:07:58

    一次AC。。。。

    最讨厌树了....

    我的树太弱了,现在来训练下!

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

    编译通过...

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

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

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

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

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

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

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

  • 0
    @ 2009-10-26 10:45:44

    很简单的TreeDP,但是处理前序遍历比较麻烦。

    可以考虑设数组t,记录l,r区间中的根是哪一个。

    最后晒一下程序,50AC。

    program cl(input,output);

    var n,i:longint;

    a:array[1..30]of longint;

    ans,answ:qword;

    t,f:array[1..30,1..30]of longint;

    procedure wtree(l,r:longint);

    begin

    if l>r then exit;

    write(t[l,r],' ');

    wtree(l,t[l,r]-1);

    wtree(t[l,r]+1,r);

    end;

    function tree(l,r:longint):qword;

    var j,tr:longint;

    begin

    if l>r then exit(1);

    if l=r then

    begin

    t[l,l]:=l;

    exit(a[l]);

    end;

    tree:=0;

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

    for j:=l to r do

    begin

    tr:=tree(l,j-1)*tree(j+1,r)+a[j];

    if tr>tree then

    begin

    tree:=tr;

    f[l,r]:=tr;

    t[l,r]:=j;

    end;

    end;

    end;

    begin

    readln(n);

    for i:=1 to n do

    read(a[i]);

    for i:=1 to n do

    begin

    answ:=tree(1,i-1)*tree(i+1,n)+a[i];

    if answ>ans then

    begin

    ans:=answ;

    t[1,n]:=i;

    end;

    end;

    writeln(ans);

    wtree(1,n);

    end.

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

    var

    a:array[1..30] of longint;

    max,i,j,q,k,n:longint;

    f:array [-1..30,-1..30] of longint;

    procedure try(x,y:longint);

    var

    i:integer;

    begin

    if x>y then exit;

    if x=y then begin write(x,' '); exit; end;

    for i:=0 to y-x do

    if f[x,x+i-1]*f[x+i+1,y]+f[x+i,x+i]=f[x,y] then

    begin

    write(x+i,' ');

    try(x,x+i-1);

    try(x+i+1,y);

    exit;

    end;

    end;

    begin

    assign(input,'binary.in');

    assign(output,'binary.out');

    reset(input);rewrite(output);

    readln(n);

    for i:=-1 to 30 do

    for j:=-1 to 30 do f:=1;

    for i:=1 to n do read(a[i]);

    for i:=1 to n do f:=a[i];

    for i:=2 to n do

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

    begin

    q:=i+j-1;

    max:=0;

    for k:=0 to i-1 do

    if f[j,j+k-1]*f[j+k+1,q]+f[j+k,j+k]>max then max:=f[j,j+k-1]*f[j+k+1,q]+f[j+k,j+k];

    f[j,q]:=max;

    end;

    writeln(f[1,n]);

    try(1,n);

    close(input);

    close(output);

    end.

    花了10分终于AC了

    纪念第79题

信息

ID
1100
难度
2
分类
动态规划 | 树形DP 点击显示
标签
递交数
4705
已通过
2626
通过率
56%
被复制
19
上传者