151 条题解
-
0
lyzhwsh LV 8 @ 2009-10-27 20:06:31
感谢LX神牛的多叉树转二叉树的思想,这次noip我有预感...
-
0
shenyanghua LV 8 @ 2009-10-26 19:09:01
用取多数塔的方法貌似勉强能过。但太麻烦-，-去看树状DP。。。
-
0
zhangyq987 LV 8 @ 2009-10-24 22:55:35
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0mstype
aa=record
da,l,r:integer;
end;
var
a:array[0..300]of aa;
f:array[0..300,0..300]of integer;
m,n,i,j,k,fa:integer;
function find(x:integer):integer;
begin
if a[x].r=0 then exit(x)
else exit(find(a[x].r));
end;
function max(a,b:integer):integer;
begin
if a>b then exit(a)
else exit(b);
end;
function work(fa,k:integer):integer;
var
now,i:integer;
begin
if fa=0 then exit(0);
if f[fa,k]>=0 then exit(f[fa,k]);
now:=0;
for i:=0 to k-1 do
now:=max(now,(work(a[fa].l,i)+work(a[fa].r,k-i-1)+a[fa].da));
now:=max(now,work(a[fa].r,k));
f[fa,k]:=now;exit(now);
end;
begin
readln(n,m);
fillchar(f,sizeof(f),128);
for i:=1 to n do
begin
readln(fa,a[i].da);
if a[fa].l=0 then a[fa].l:=i
else a[find(a[fa].l)].r:=i;
f:=0;
end;
write(work(a[0].l,m));
end.AC的第一个树形DP 秒杀O(∩_∩)O哈！
-
0
yjl3567618 LV 8 @ 2009-10-24 11:10:57
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 119ms
├ 测试数据 05：答案正确... 228ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：347mstype
tree=record
l,r,k:longint;
end;
var i,j,k,n,m,l:longint;
a:array[0..301] of tree;
f:array[0..301] of longint;
b:array[-10..301,-10..301] of longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a
else max:=b;
end;
procedure try(x,y:longint);
var i,j,k,l:longint;
begin
if b[x,y]>=0 then exit;
try(a[x].r,y);
b[x,y]:=b[a[x].r,y];
for k:=1 to y do
begin
try(a[x].l,k-1);
try(a[x].r,y-k);
b[x,y]:=max(b[x,y],b[a[x].l,k-1]+b[a[x].r,y-k]+a[x].k);
end;
end;
begin
read(n,m);
for i:=1 to n do
begin a[i].l:=-1;a[i].r:=-1;a[i].k:=-1;end;
for i:=1 to n do
begin
read(k,l);
readln;
a[i].k:=l;
if f[k]=0 then a[k].l:=i
else a[f[k]].r:=i;
f[k]:=i;
end;
for i:=-1 to n do
for j:=-1 to m do
if (i=-1) or (j=0) then b:=0 else b:=-1;
try(a[0].l,m);
writeln(b[a[0].l,m]);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms打错一个地方，调了一个半小时，无语。
不过还好终于赶上了：第1200个AC
Flag Accepted
题号 P1180
类型(?) 动态规划
通过 1200人
提交 2987次
通过率 40%
难度 2 -
0
好简单的递归求树形动归（背包合并）啊，竟然有这么多小粗心，有罪啊！！
巧妙的利用函数进行递归，大家自己体会吧
var n,m,i,j,r,q,k:longint;
a,f:array[0..500,1..500] of longint;
p,l,fu:array[0..500] of longint;function dfs(r:longint):longint;
var s,j,i,k,er:longint;
begin
dfs:=1; f[r,1]:=p[r];
for i:=1 to l[r] do
begin
er:=a[r,i]; s:=dfs(er);
for j:=dfs downto 1 do
for k:=1 to s do if f[r,j]+f[er,k]>f[r,j+k] then f[r,j+k]:=f[r,j]+f[er,k];
inc(dfs,s);
end;
end;begin
readln(n,m);
for i:=1 to n do
begin
readln(r,p[i]); fu[i]:=r;
inc(l[r]); a[r,l[r]]:=i;
end;
dfs(0);
writeln(f[0,m+1]);
end. -
0
#include
using namespace std;
int n,m;
int a[301],b[301],c[301][301],d[301][301],dp[301];
bool flog[301];
int max(int a,int b)
{
return a>b?a:b;
}
void dfs(int num,int sum,int h,int k,int l)
{
for(int i=1;i>n>>m;
for(i=1;i>a[i]>>b[i];
memset(flog,false,sizeof(flog));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(i=1;i -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms树形dp……练手的
program v1108;
var f:array[0..301,0..301] of longint;
w,r,l,nu:array[0..301] of longint;
i,n,m,root,x,j:longint;
function max(p,q:longint):longint;
begin
if p>q then exit(p) else exit(q);
end;
function min(p,q:longint):longint;
begin
if pnu[i])or(f>0)
then exit;
for k:=min(j-1,nu[l[i]]) downto 0 do
begin
t:=j-k-1;
if t>nu[r[i]] then exit;
dp(l[i],k);
dp(r[i],t);
f:=max(f,f[l[i],k]+w[i]+f[r[i],t]);
end;
if (nu[r[i]]>=j)and(nu[r[i]]>0)
then begin
dp(r[i],j);
f:=max(f,f[r[i],j]);
end;
end;
begin
readln(n,m);
root:=0;
for i:=1 to n do
begin
readln(x,w[i]);
if (x=0)and(root=0)
then root:=i;
if l[x]=0
then l[x]:=i
else begin
r[i]:=r[l[x]];
r[l[x]]:=i;
end;
end;
dfs(root);
dp(root,m);
writeln(f[root,m]);
end. -
0
不容易啊！！！！！
这道题我想了3天，看了SDSC2009夏令营的lpyの绿书，结合楼下校友liujiahui的程序。
终于在今天背过并理解了。（我昨天可是熬夜很晚还在看OI）
今天一口气默写出来了
但是一开始始终不对，找啊找啊……很久很久……
原来是我一直不是很明白的多叉树转二叉树，lpyの绿书上把这么重要的东西给写错了！！！万恶的lpy……
因为下面的程序多叉树转二叉树写的都很诡异，所以只好自己推了个代码：
我怎么这么鄙视lpy……虽然这样非常降RP……
万恶的 多叉树转二叉树
for i:=1 to n do
begin
readln(x,a[i]);if (x=0)and(root=0)then root:=i;
if l[x]=0 then l[x]:=i
else begin
r[i]:=r[l[x]];r[l[x]]:=i;
end;
end;编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms没有人比我的程序更简练了吧……（因为没有用记录，数组名字简单）
const filename='p1180';
var
f:array[0..300,0..300]of longint;
i,j,k,m,n,root,x:longint;
a,l,r:array[1..300]of longint;
function max(x,y:longint):longint;
begin if x>y then exit(x);exit(y);end;
procedure dp(i,j:longint);
var k:longint;
begin
if (i=0)or(j=0)then exit;
if (f0)then exit;
dp(r[i],j);
f:=f[r[i],j];
for k:=1 to j do
begin
dp(l[i],k-1);
dp(r[i],j-k);
f:=max(f,f[l[i],k-1]+a[i]+f[r[i],j-k]);
end;
end;
begin
assign(input,filename+'.in');reset(input);
assign(output,filename+'.out');rewrite(output);
readln(n,m);root:=0;
for i:=1 to n do
begin
readln(x,a[i]);if (x=0)and(root=0)then root:=i;
if l[x]=0 then l[x]:=i
else begin
r[i]:=r[l[x]];r[l[x]]:=i;
end;
end;
dp(root,m);
writeln(f[root,m]);
close(input);close(output);
end. -
0
yzl609271536 LV 10 @ 2009-09-02 09:39:54
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms树形DP 秒杀
-
0
prince_hao LV 10 @ 2009-08-31 17:55:01
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msprogram p1180;
type node=record
l,r,d:integer;
end;
var f:array[0..100000]of integer;
t:array[0..10000]of node;
opt:array[0..1000,0..1000]of longint;
n,m:integer;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure init;
var i,j,x,y:integer;
begin
readln(n,m);
for i:=1 to n do
begin
read(x,y);
if f[x]=0 then
t[x].l:=i
else
t[f[x]].r:=i;
f[x]:=i;
t[i].d:=y;
end;
end;
function dp(i,j:integer):longint;
var k,l,o:integer;
begin
if j=0 then exit(0);
if opt0 then exit(opt);
if (t[i].l=0)and(t[i].r=0) then
begin
if j=1 then opt:=t[i].d;
end
else if (t[i].l=0) then
begin
opt:=max(dp(t[i].r,j-1)+t[i].d,dp(t[i].r,j));
end
else if (t[i].r=0) then
begin
opt:=dp(t[i].l,j-1)+t[i].d;
end
else
begin
opt:=dp(t[i].r,j);
for k:=0 to j-1 do
opt:=max(dp(t[i].l,k)+dp(t[i].r,j-k-1)+t[i].d,opt);
end;
dp:=opt;
end;
begin
init;
writeln(dp(0,m+1));
end.
lyzhwsh
LV 8
@ 2009-10-27 20:06:31
