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

NOIP2003 的几题都挺不错的

...第100题献给1100

重新看了遍题目。。原来我会做。-，-

心情舒畅。。。但是估计又要在细节上错很多

编译通过...

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

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

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

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

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

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

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

var a:array[0..1003]of longint;

f,w:array[0..40,0..40]of longint;

n,i,j,k:longint;

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

begin

if x>y then max:=x else

begin

max:=y;

w:=k;

end;

end;

procedure find(l,r:longint);

begin

if l=r then write(l,' ')

else

if l>r then exit

else

begin

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

find(l,w[l,r]-1);

find(w[l,r]+1,r);

end;

end;

begin

readln(n);

fillchar(f,sizeof(f),0);

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

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

for i:=n downto 1 do

for j:=i+1 to n do

begin

k:=j;

f:=max(f,f+f[j,j]);

k:=i;

f:=max(f,f+f);

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

f:=max(f,f*f[k+1,j]+a[k]);

end;

writeln(f[1,n]);

find(1,n);

end.

Flag 　　 Accepted

题号 　　P1100

类型(?) 　　动态规划

通过 　　3020人

提交 　　5272次

通过率 　　57%

难度 　　2

过的第一道树型动规

dp里的合并类型 + 树结构的基础知识

跟班数组

递归求解

呃...这题通过率好高- -

program binary;

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

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

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

function fm(x,y:longint):longint;

var g,t,s,l:longint;

begin

if x>y then begin fm:=1; exit; end;

if f[x,y]0 then exit(f[x,y]);

s:=x; f[x,y]:=fm(x+1,y)+a[x];

if fm(x,y-1)+a[y]>f[x,y] then begin

f[x,y]:=fm(x,y-1)+a[y];s:=y; end;

for g:=x+1 to y-1 do

if fm(x,g-1)*fm(g+1,y)+a[g]>f[x,y] then

begin f[x,y]:=fm(x,g-1)*fm(g+1,y)+a[g];s:=g; end;

r[x,y]:=s;

exit(f[x,y]);

end;

procedure print(x,y:longint);

begin

if x>y then exit;

if (x=1) and (y=n) then write(r[x,y]) else write(' ',r[x,y]);

print(x,r[x,y]-1);print(r[x,y]+1,y);

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;

writeln(fm(1,n));

print(1,n);

writeln;

end.

终于A了。。

题解 http://254117343.blog.163.com/

编译通过...

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

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

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

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

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

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

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

水题水题!!!!!

编译通过...

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

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

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

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

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

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

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

一次Ac……纪念一下6

强大的DP=AC

此题我做久矣。

编译通过...

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

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

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

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

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

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

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

难度为二的动规我也能凭自己的聪明才智一次AC了，真激动，特此留念……

动态规划

f代表子序列a[i]到a[j]的最大加分

g代表根的序号

以下是特殊情况

1.f=a[i] g=i

2.f=1 子树为空,没有g

3.f[n,n+1]=1 子树为空,没有g[n,n+1]

如果f=0,也就是f没有被求出来，不属于特殊情况时

f=max(f[k,k]+f*f[k+1,j])

g=k

注:1.max代表求最大值

2.k可以用循环来枚举

3.f代表左子树加分

4.f[k+1,j]代表右子树加分

program lx;

var

n,i,k :longint;

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

visit :array[1..30,1..30]of longint;

tree :array[1..50,1..50]of longint;

procedure print(i,j:longint);

begin

if i>j then exit;

if i=j then begin

write(i,' ');

exit;

end;

write(tree,' ');

print(i,tree-1);

print(tree+1,j);

end;

function work(i,j:longint):longint;

var

t,m,temp,root :longint;

begin

if i>j then begin

work:=1;

exit;

end;

if i=j then begin

work:=a[i];

exit;

end;

if visit0 then begin

work:=visit;

exit;

end;

m:=0;

root:=0;

for t:=i to j do begin

temp:=work(i,t-1)*work(t+1,j)+a[t];

if m

var

n,k :longint;

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

tree :array[1..50,1..50]of longint;

visit :array[1..50,1..50]of longint;

root :longint;

function f(i,j:longint):longint;

var

t,m,temp,root :longint;

begin

if i>j then exit(1);

if i=j then exit(a[i]);

if visit[i][j]0 then exit(visit[i][j]);

m:=0;

root:=0;

for t:=i to j do begin

temp:=f(i,t-1)*f(t+1,j)+a[t];

if mj then exit;

if i=j then begin

write(i,' ');

exit;

end;

write(tree[i][j],' ');

print(i,tree[i][j]-1);

print(tree[i][j]+1,j);

end;

begin

readln(n);

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

writeln(f(1,n));

print(1,n);

end.

递归+记忆化

有个很奇怪的问题希望有人能解答一下

一开始没有这句if f[l,r]0 then exit;

的时候超时了

加了这句就秒杀

为什么呢？

第一次在vijos上一次AC一树，居然是难度2的，还是noip的~~

一遍AC~！~

f:=max{f*f[k+1,j]+a[k]};

在开个数组记录根节点就行了~

最后递规输出先序遍历~

var

n,i,j,k,l,r:longint;

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

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

procedure pre(l,r:longint);

begin

if l>r then exit;

if l=r then begin write(l,' '); exit; end;

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

pre(l,d[l,r]-1);

pre(d[l,r]+1,r);

end;

Begin

readln(n);

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

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

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

var

a:array[0..50] of integer;

f,g:array[0..1000,0..1000] of cardinal;

i,j,k,n:longint;

procedure tree(x,y:longint);

begin

if (x=x then

tree(x,g[x,y]-1);

if g[x,y]+1