谁帮我解答一个关于Pascal的问题(NOIP2003提高组binary加分二叉树)

2024-12-21 01:24:00
推荐回答(4个)
回答1:

动态规划
f[i,j]代表子序列a[i]到a[j]的最大加分
g[i,j]代表根的序号
以下是特殊情况
1.f[i,i]=a[i] g[i,i]=i
2.f[i,i-1]=1 子树为空,没有g[i,i-1]
3.f[n,n+1]=1 子树为空,没有g[n,n+1]
如果f[i,j]=0,也就是f[i,j]没有被求出来,不属于特殊情况时
f[i,j]=max(f[k,k]+f[i,k-1]*f[k+1,j])
g[i,j]=k
注:1.max代表求最大值
2.k可以用循环来枚举
3.f[i,k-1]代表左子树加分
4.f[k+1,j]代表右子树加分
以下是程序(vijos上通过了)
program aa;
var
n,i,j,k:longint;
a:array[1..30] of longint;
f,g:array[1..30,0..31] of longint;
procedure print(i,j:longint);
begin
write(g[i,j],' ');
if i<=g[i,j]-1 then print(i,g[i,j]-1);
if g[i,j]+1<=j then print(g[i,j]+1,j);
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
begin
f[i,i]:=a[i];
g[i,i]:=i;
f[i,i-1]:=1;
end;
f[n,n+1]:=1;
for i:=n downto 1 do
for j:=i to n do
if f[i,j]=0 then
begin
for k:=i to j do
if f[k,k]+f[i,k-1]*f[k+1,j]>f[i,j] then
begin
f[i,j]:=f[k,k]+f[i,k-1]*f[k+1,j];
g[i,j]:=k;
end;
end;
writeln(f[1,n]);
print(1,n);
writeln;
end.

回答2:

动态规划,
兰州可以想一下,对于中序遍历是子序列a[i..j],并且k(i<=k<=j)为跟的一个二叉树,那么子序列a[i..k-1]是左子树,a[k+1..j]是右子树,无疑这两个子序列的加分分别要最大.所以我们用动态规划,设dp[i,j]是子序列a[i..j]的最大加分,每次枚举根k,时间复杂度O(n^3);

回答3:

程序我有,vijos上AC了的
program NOIP_2003_3;
var f:array[0..30,0..30]of longword;
root:array[1..30,1..30]of integer;
a:array[1..30]of integer;
i,j,k,n,p:longint;
procedure init;
begin
readln(n);
for i:=1 to n do
read(a[i]);
fillchar(f,sizeof(f),0);
fillchar(root,sizeof(root),0);
for i:=0 to n do
for j:=0 to n do
f[i,j]:=1;
for i:=1 to n do
begin
f[i,i]:=a[i];
root[i,i]:=i;
end;
end;
procedure pre(i,j:integer);
begin
if i<=j then begin
write(root[i,j],' ');
pre(i,root[i,j]-1);
pre(root[i,j]+1,j);
end;
end;
begin
init;
for p:=1 to n-1 do
for i:=1 to n-p do
begin
j:=i+p;
f[i,j]:=0;
for k:=i to j do
if f[i,k-1]*f[k+1,j]+a[k]>f[i,j] then begin
f[i,j]:=f[i,k-1]*f[k+1,j]+a[k];
root[i,j]:=k;
end;
end;
writeln(f[1,n]);
pre(1,n);
end.
分给LS把,分对我来说不重要了现在

回答4:

恩?

这不是oibh上的gnaggnoyil 牛吗?在这现身了啊!膜拜..

树形DP,递归求解.很好写的