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

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

i,j,k,l,max,n,o,p:longint;

procedure print(x,y:longint);

begin

write(g[x,y],' ');

if xmax then begin max:=f; end;

end;

writeln(max);

print(1,n);

end.

看了mq_miqing的代码才会做的 在此谢过 （只是输出的时候会不会在答案最后多一个空格？NOIP的测试可是全文比较啊）

还有，大家的做法都比较象记忆化搜索，而不是DP啊（不过看到DP的处理，有点麻烦）。

另外，《树型动态规划的实例分析》某牛的报告，很不错的

program p1100;

const

maxn=30;

var

n:longint;

value:array[1..maxn] of longint;

f:array[0..maxn,0..maxn] of longint;

root: array[1..maxn,1..maxn] of longint;

procedure init;

var

i:longint;

begin

readln(n);

for i:=1 to n do

　　read(value[i]);

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

fillchar(root,sizeof(root),0);

end;

procedure treeDp(l,r:longint);

var

i,t:longint;

begin

if l>r then

　　begin

　　 f[l,r]:=1;

　　 exit;

　　end;

if l=r then

　　begin

　　 f[l,r]:=value[l];

　　 root[l,r]:=l;

　　 exit;

　　end;

if f[l,r]0 then exit;

for i:=l to r do

　　begin

　　 treeDp(l,i-1);

　　 treeDp(i+1,r);

　　 t:=value[i]+f[l,i-1]*f;

　　 if t>f[l,r] then

　　　　begin

　　　　 f[l,r]:=t;

　　　　 root[l,r]:=i;

　　　　end;

　　end;

end;

procedure preOrder(l,r:integer);

begin

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

if l

program p1100;

const

maxn=30;

var

n:longint;

value:array[1..maxn] of longint;

f:array[0..maxn,0..maxn] of longint;

root: array[1..maxn,1..maxn] of longint;

procedure init;

var

i:longint;

begin

readln(n);

for i:=1 to n do

read(value[i]);

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

fillchar(root,sizeof(root),0);

end;

procedure treeDp(l,r:longint);

var

i,t:longint;

begin

if l>r then

begin

f[l,r]:=1;

exit;

end;

if l=r then

begin

f[l,r]:=value[l];

root[l,r]:=l;

exit;

end;

if f[l,r]0 then exit;

for i:=l to r do

begin

treeDp(l,i-1);

treeDp(i+1,r);

t:=value[i]+f[l,i-1]*f;

if t>f[l,r] then

begin

f[l,r]:=t;

root[l,r]:=i;

end;

end;

end;

procedure preOrder(l,r:integer);

begin

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

if l

卡了三年了...原来明白是道卡语文的题

30行轻松搞定

备注：不用int64或qword也可以，用longword(0..2^32-1)

解题报告：

题意分析

1、在中序遍历为（1,2,3,…,n）的各种二叉树中，选出加分最高的一棵二叉树，输出最高加分和对此二叉树的前序遍历。

加分规则：任意棵子树subtree（也包含tree本身）的加分计算方法如下：

subtree的左子树的加分*subtree的右子树的加分+subtree的根的分数

若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数，不考虑它的空子树。

2、输入：节点数和每个节点的分值。（n

算法分析

因为给出中序遍历（1,2,3,…,n），所以可以以每个节点作根。

当根为i时，则将序列分为三部分1至（i-1）为左子树，i为根，（i+1）至n为右子树。根据上面分析可断定此题可利用动态规划解决。

编译通过...

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

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

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

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

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

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

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

交了5次 不说什么了

很好的树形动规练习题，递推方程不好推的话用记忆搜索也不错

program vijos1100; { 加分二叉树 }

const

maxn=30;

var

n:longint;

value:array[1..maxn] of longint;

f: array[0..maxn,0..maxn] of longint;

root: array[1..maxn,1..maxn] of longint;

procedure init;

var

i:longint;

begin

readln(n);

for i:=1 to n do

read(value[i]);

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

fillchar(root,sizeof(root),0);

end;

procedure treeDp(l,r:longint);

var

i,t:longint;

begin

if l>r then begin f[l,r]:=1; exit; end;

if l=r then begin f[l,r]:=value[l]; root[l,r]:=l; exit; end;

if f[l,r]0 then exit;

for i:=l to r do

begin

treeDp(l,i-1);

treeDp(i+1,r);

t:=value[i]+f[l,i-1]*f;

if t>f[l,r] then

begin f[l,r]:=t; root[l,r]:=i; end;

end;

end;

procedure preOrder(l,r:integer);

begin

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

if l

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

Unaccepted 有效得分：0 有效耗时：0ms

这个是什么情况。。。

树型DP

var

i,n:longint;

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

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

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

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

var

i:longint;

begin

dfs:=0;

if x>y then

begin

dfs:=1;

exit;

end;

if x=y then

begin

dfs:=a[x];

t[x][y]:=x;

exit;

end;

if v[x][y]>0 then

begin

dfs:=v[x][y];

exit;

end;

for i:=x to y do

if dfsy then exit;

write(t[x][y],' ');

if x

#include

using namespace std;

long long f[101][101];

int boot[101][101];

void search(int lx,int rx)

{

cout

编译通过...

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

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

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

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

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

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

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

downto 打成了 to 好我提交了好几次

...........

var

n,i,j,k,l:integer;

p:array[1..30]of integer;

f:array[0..31,0..31]of cardinal;

root:array[1..30,1..30]of integer;

s:array[1..30]of integer;

procedure dfs(i,j:integer);

begin

if k=n then exit;

inc(k);

s[k]:=root;

if root-1>=i then dfs(i,root-1);

if root+1

编译通过...

├ 测试数据 01：答案错误...程序输出比正确答案长

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案错误...程序输出比正确答案长

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

Unaccepted 有效得分：0 有效耗时：0ms

郁闷

编译通过...

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

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

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

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

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

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

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

O(n^3)的

枚举树根

然后

。。。

...

f=max{f*f[k+1,j]+w[k]}

然后

。。。

...

没了。。

这天底下什么怪事都有，而且都被我摊上了，这RP杠杠的！！

比如

写：

read(temp);

f:=temp;

way:=i;

写对

但是，如果写。。。。。

read(f);

way:=i;

就错！！！！！！！

是不是我比较不见多识广啊

有没有大牛告诉我下那里错了，嘿！

还有函数中写exit(xxxx)的话，错！

写 search:=xxxx;对！

难道是。。。。。。。。。。。。

感动之余要感谢石子归并.

注意要考虑两种边界情况:

对于任何一个根节点

1.只有一棵子树;

2.没有子树.

接下来的Dp,我就不多说了吧

HERSELF告诉我状态转移方程

还说最好的方法是记忆化搜索。。。

我不会，于是，我用了DP，再加一个二维数组记录区间[L，R]的根

之后又用DFS输出前序遍历，结果：

编译通过...

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

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

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

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

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

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

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

程序总长26行。。。最后，庆祝下第90题~~AC~~ ^-^