題目大意

?? 對于一個二叉樹，除根節(jié)點外，每個節(jié)點都有相應(yīng)的一個權(quán)值。在此基礎(chǔ)上，求保留多少個點使得其仍然滿足樹的性質(zhì)且權(quán)值總和最大。

分析

? 具體方法見：http://blog.csdn.net/a_loud_name/article/details/51326123

代碼

varf:array[0..200,0..200] of longint;a:array[0..200,1..3] of longint;b:array[0..200,0..200] of longint;v,num:array[0..200] of longint;i,j,k,l:longint;n,m,nm:longint;ans:longint;procedure make(v:longint); vari,j,k:longint; beginfor i:=1 to n dobeginif b[v,i]>0 thenbegina[v,1]:=i;num[i]:=b[v,i]-1;b[v,i]:=-1; b[i,v]:=-1;make(i);break;end;end;for i:=1 to n dobeginif b[v,i]>0 thenbegina[v,2]:=i;num[i]:=b[v,i]-1;b[v,i]:=-1; b[i,v]:=-1;make(i);break;end;end; end;procedure dfs(r,l:longint); vari,j,k:longint; beginif f[r,l]<>0 then exit;if l=0thenbeginf[r,l]:=0;exit;end;if (a[r,1]=0) and (a[r,2]=0)then beginf[r,l]:=num[r];exit;end;for i:=0 to l-1 dobegindfs(a[r,1],i);dfs(a[r,2],l-i-1);if f[r,l]<f[a[r,1],i]+f[a[r,2],l-i-1]+num[r]thenf[r,l]:=f[a[r,1],i]+f[a[r,2],l-i-1]+num[r];end; end;beginreadln(n,m,nm);m:=m+1;for i:=1 to n-1 dobeginreadln(j,k,l);b[j,k]:=l+1;b[k,j]:=l+1;end;fillchar(f,sizeof(f),0);fillchar(v,sizeof(v),0);fillchar(a,sizeof(a),0);v[0]:=1;make(1);dfs(1,m);if nm<=f[1,m] then writeln('TRUE')else writeln('FALSE');writeln(f[1,m]-nm); end.

轉(zhuǎn)載于:https://www.cnblogs.com/a-loud-name/p/6184822.html

總結(jié)

以上是生活随笔為你收集整理的将功补过 树形动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。