好水，，不过我也是一次AC啊。。。点击查看AC源码

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: 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);
}

#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;
}

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.

###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;
}

水水的..

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.

区间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.

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

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

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.

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

第二问太邪恶了。。

非要字典序输出..

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

第二次在转移时打了

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

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

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

= =~``

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.

一次AC。。。。

最讨厌树了....

我的树太弱了，现在来训练下！

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

编译通过...

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

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

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

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

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

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

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

很简单的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.

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题