151 条题解
-
0
tkxhdm LV 3 @ 2008-11-04 20:21:21
不,是我看错了....
-
0
[非2叉树]
program Project1;
var n,m,k,y:longint;
w,id:array[0..1000]of longint;
od,f:array[0..301,0..301]of longint;
temp:array[0..100,0..301,0..301]of longint;
procedure goal(depth,x:longint);
var i,j,max,t:longint;
begin
if id[x]=0 then
begin
f[x,1]:=w[x];
exit;
end;
for i:=0 to n do
for j:=0 to n do temp[depth,i,j]:=0;
for i:=1 to id[x] do
begin
goal(depth+1,od[x,i]);
for j:=1 to m do
begin
max:=0;
for t:=0 to j do
if temp[depth,i-1,t]+f[od[x,i],j-t]>max then max:=temp[depth,i-1,t]+f[od[x,i],j-t];
temp[depth,i,j]:=max;
end;
end;
for j:=1 to m do f[x,j]:=temp[depth,id[x],j-1]+w[x];
end;begin
readln(n,m);
for k:=1 to n do
begin
readln(y,w[k]);
inc(id[y]);
od[y,id[y]]:=k;
end;
goal(0,0);
write(temp[0,id[0],m]);
end.[2叉树]
program N1180;
var p:array[0..301]of record
lch,rch:longint;
end;
w,forest:array[0..301]of longint;
f,ans:array[-1..301,-1..301]of longint;
i,j,k,n,m,y:longint;
procedure makef(i:longint);
var j,t:longint;
begin
if i=-1 then exit;
if (p[i].lch=-1) and (p[i].rch=-1) then
begin
f:=w[i];
exit;
end;
makef(p[i].lch);makef(p[i].rch);
for j:=1 to m do
begin
f:=f[p[i].rch,j];
for t:=1 to j do
if w[i]+f[p[i].lch,t-1]+f[p[i].rch,j-t]>f then f:=w[i]+f[p[i].lch,t-1]+f[p[i].rch,j-t];
end;
end;begin
readln(n,m);
for i:=1 to n do begin p[i].lch:=-1;p[i].rch:=-1; end;
for i:=1 to n do
begin
readln(y,w[i]);
if y=0 then
begin
inc(forest[0]);
forest[forest[0]]:=i;
end
else
begin
if p[y].lch=-1 then
begin
p[y].lch:=i;
end
else
begin
y:=p[y].lch;
while p[y].rch-1 do y:=p[y].rch;
p[y].rch:=i;
end;
end;
end;for i:=1 to forest[0] do
begin
makef(forest[i]);
for j:=1 to m do
for k:=0 to j do
if ans+f[forest[i],j-k]>ans then ans:=ans+f[forest[i],j-k];
end;writeln(ans[forest[0],m]);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms不用转二叉树
直接DPprogram p1180;
var i,j,k,m,n,wh:longint;
a:array[0..300,0..300]of longint;
f:array[0..300,0..300]of longint;
s:array[0..300]of longint;
w,num:array[0..300]of longint;
procedure work(v:longint);
var i,j:longint;
begin
for i:=1 to num[v] do work(a[v][i]);
fillchar(s,sizeof(s),0);
for i:=1 to num[v] do
begin
for j:=m downto 0 do
begin
for k:=0 to m do
if j+ks[j+k] then s[j+k]:=s[j]+f[a[v][i]][k];
end;
end;
if v=0 then
begin
write(s[m]);
halt;
end
else
for i:=1 to m do f[v][i]:=s+w[v];
end;
begin
readln(n,m);
fillchar(num,sizeof(num),0);
for i:=1 to n do
begin
readln(wh,w[i]);
inc(num[wh]);
a[wh,num[wh]]:=i;
end;
work(0);
end. -
0
type
tree=record
k,l,r:integer;end;{K：该节点的值；L：左子树的根节点；R：右子树的根节点}
var f:array[0..200]of integer;
a:array[0..200]of tree;
{a数组为树数组，左子树放第i节点的儿子，右子树放兄弟}
b:array[-1..200,-1..200]of longint;
{b表示以第i个节点为根的树取j个节点的最大值，根节点一定要取的拉。。}---|---|---|---|---|---|---|---|我是无敌分割线---|---|---|---|---|---|---|---|--
build tree喽（PS：还有点不熟练。。郁闷。。之前没初始化。SO 死循环- -入肉啊。。。。。）。。then。。
treedp（X，Y）：（X表示第X个节点，Y表示取Y个节点）
{
先遍历右子树；（PS：因为是兄弟啊，所以可以不取第i个节点。所以递归取的节点还是Y个。）
遍历完，b[x,y]附值。就是右子树的值。
开始遍历左子树。。
{
b[x,y]:=max(b[a[x].l,k]+a[x].k+b[a[x].r,y-k-1]┃0 -
0
很简单的动规方程：
f:=max{f[k,t[j].lch]+f[i-k-1,t[j].rch]+v[j],f[i,t[j].rch]}一边递归，一边记录。
名言：
光记录不递归是错误的；
光递归不记录是超时的。编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
zyg123456789 LV 3 @ 2008-08-21 19:24:16
本来我以为把多X树变成2X树很复杂嘞。
结果在读了每个结点的dad,w之后只加两句话...
for i:=1 to n do
begin
readln(dad,w); a[i].w:=w;
if b[dad]=0 then a[dad].lch:=i else a[b[dad]].rch:=i;
b[dad]:=i;
end;
//b数组记录该节点的最后一个儿子 -
0
太爽了…………
第一次做树形dp的题，而且一次AC……编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
我是菜鸟，不太会使指针建树，于是我用数组模拟树型结构…………
先预处理一下，存一下谁的儿子都有谁，在dpz表示i的第j个儿子（儿子顺序无所谓）（0也是父亲）
f(i,j)表示i节点还可以选j课
方程较复杂，忽略，关键是我用的是记忆化搜索，四维的…………
事实上是两维的，另外两个变量记录的是改点在z数组中的位置（为了方便）…………然后就有4种情况，左右都有，只有左，只有右，叶子………………
（已经转化成了2叉树，相信这个大家都会，自己z[~,~~]，兄弟z[~,~~+1]）
之后分情况讨论就可以了…………
tkxhdm
LV 3
@ 2008-11-04 20:21:21
