| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:二维数组,树形dp,背包转移In Reply To:这要怎么树形DP呀。。。oh my GOD~!!!!!!!!! Posted by:huangzhifei at 2011-02-24 16:07:06 > RT var a,f,d:array[0..150,0..150]of longint; v:array[0..150]of boolean; n,m,i,j,x,y,root,ans:longint; procedure treedp(x:longint); var i,j,k:longint; begin for i:=1 to a[x,0] do treedp(a[x,i]); fillchar(d,sizeof(d),127); d[0,0]:=0; for i:=1 to a[x,0] do begin for j:=0 to m do if d[i-1,j]<n then d[i,j]:=d[i-1,j]+1; for j:=1 to m do if f[a[x,i],j]<n then for k:=0 to m-j do if (d[i-1,k]<n)and(d[i-1,k]+f[a[x,i],j]<d[i,k+j]) then d[i,k+j]:=d[i-1,k]+f[a[x,i],j]; end; for j:=m-1 downto 0 do if d[i,j]<n then d[i,j+1]:=d[i,j]; if a[x,0]=0 then f[x,1]:=0; for j:=1 to m do if f[x,j]>d[i,j] then f[x,j]:=d[i,j]; if x=root then if ans>f[x,m] then ans:=f[x,m] else else if ans>f[x,m]+1 then ans:=f[x,m]+1; end; begin readln(n,m); for i:=1 to n-1 do begin readln(x,y); inc(a[x,0]); a[x,a[x,0]]:=y; v[y]:=true; end; for i:=1 to n do if not v[i] then root:=i; fillchar(f,sizeof(f),127); ans:=n; treedp(root); writeln(ans); end. Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator