vj p1038题解

原体叙述

经典区间类DP

f[i,j]:=min(f[i,k]+f[k+1,j]+sum(i,j));

记录一个最优解的路径rout[i,j]

其他的就不解释了

代码如下：

 1 var ans,n:longint;s,a:array[0..30]of longint;
 2     r,f:array[0..30,0..30]of longint;
 3 function find(i,j:longint):longint;
 4          var k,t,z:longint;
 5 begin
 6      if f[i,j]<0 then
 7         begin
 8              z:=maxlongint;
 9              for k:=i to j-1 do
10                  begin
11                       t:=find(i,k)+find(k+1,j)+s[j]-s[i-1];
12                       if t<=z then
13                          begin
14                               r[i,j]:=k;
15                               z:=t;
16                          end;
17                  end;
18              f[i,j]:=z;
19         end;
20      find:=f[i,j];
21 end;
22 procedure init;
23           var i:longint;
24 begin
25           readln(n);
26      s[0]:=0;
27      for i:=1 to n do
28          begin
29               read(a[i]);
30               s[i]:=s[i-1]+a[i];
31          end;
32           fillchar(f,sizeof(f),250);
33      for i:=0 to n do f[i,i]:=0;
34      for i:=1 to n-1 do f[i,i+1]:=s[i+1]-s[i-1];
35 end;
36 procedure print(i,j:longint);
37 begin
38      if i=j then write(a[i])
39      else
40          if i+1=j then write('(',a[i],'+',a[j],')')
41          else
42              begin
43                   write('(');
44                   print(i,r[i,j]);
45                   write('+');
46                   print(r[i,j]+1,j);
47                   write(')');
48              end;
49 end;
50 procedure addout(i,j:longint);
51 begin
52      if i=j then exit;
53      if i+1=j then
54         begin
55              write(s[j]-s[i-1],' ');
56         end
57      else
58          begin
59               addout(i,r[i,j]);
60               addout(r[i,j]+1,j);
61               write(s[j]-s[i-1],' ');
62          end;
63 
64 end;
65 begin
66      init;
67      ans:=find(1,n);
68 
69      print(1,n);
70      writeln;
71      writeln(ans);
72      addout(1,n);
73 end.