tree-dp理解與運用.doc

樹型動態(tài)規(guī)劃講解樹型動態(tài)規(guī)劃是動態(tài)規(guī)劃中的一種比較特殊的種類，他的特殊，在于這種動態(tài)規(guī)劃在樹這種數(shù)據(jù)結(jié)構(gòu)上。所以這種動態(tài)規(guī)劃就結(jié)合了樹的特點。使用遞歸方式解答。狀態(tài)總是通過每層來劃分的，并且從也節(jié)點到根的方向進行狀態(tài)轉(zhuǎn)移（反過來也可，但不簡便）。樹再這里有兩種分類，一種是有根樹，一種是無根樹。在一棵樹中，一旦根確定，就意味著這顆樹的結(jié)構(gòu)也就確定了。所以有根樹比無根樹相對簡單一些。無根樹分為兩種情況，依題目而異。有些題目中，答案是和樹的形態(tài)沒有關(guān)系的，此時我們只需要隨機選取一個節(jié)點作為根建樹即可。還有些題目，答案和樹的形態(tài)有關(guān)系，此時我們必須要枚舉每個節(jié)點作為跟的情況進行建樹，求解，才可以得到答案。Ural 1018二叉蘋果樹（有根樹,二叉樹dp）題目有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有只有1個兒子的結(jié)點）這棵樹共有N個結(jié)點（葉子點或者樹枝分叉點），編號為1-N,樹根編號一定是1（從這個條件可以判斷這個樹是有根樹）。我們用一根樹枝兩端連接的結(jié)點的編號來描述一根樹枝的位置。下面是一顆有4個樹枝的樹 2 5 / 3 4 / 1現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。輸入格式第1行2個數(shù)，N和Q(1=Q= N,1N=100)。N表示樹的結(jié)點數(shù)，Q表示要保留的樹枝數(shù)量。接下來N-1行描述樹枝的信息。每行3個整數(shù)，前兩個是它連接的結(jié)點的編號。第3個數(shù)是這根樹枝上蘋果的數(shù)量。每根樹枝上的蘋果不超過30000個。輸出格式一個數(shù)，最多能留住的蘋果的數(shù)量。樣例輸入5 21 3 11 4 102 3 203 5 20樣例輸出21題目地址：http:/acm.timus.ru/submit.aspx?space=1&num=1039解析：因為題目一給出就是二叉的，所以很容易就可以寫出方程：a(I,j):=max(a(i.left,k)+a(i.right,j-k),0=k0 then for i:=1 to q do for j:=0 to i-1 do begin t:=dpx,1+dpc1,j+dpc2,i-1-j; if tdpx,i then dpx,i:=t; end; end;begin read(n,q);inc(q); for i:=1 to n-1 do read(v1i,v2i,applei); dfs(1); writeln(dp1,q);end.Ural 1039 沒有上司的晚會（普通樹，有根樹DP）背景有個公司要舉行一場晚會。為了能玩得開心，公司領(lǐng)導(dǎo)決定：如果邀請了某個人，那么一定不會邀請他的上司（上司的上司，上司的上司的上司都可以邀請）。題目每個參加晚會的人都能為晚會增添一些氣氛，求一個邀請方案，使氣氛值的和最大。輸入格式第1行一個整數(shù)N（1=N=6000）表示公司的人數(shù)。接下來N行每行一個整數(shù)。第i行的數(shù)表示第i個人的氣氛值x(-128=xb then max:=a else max:=b; end;procedure dfs(v:word); begin while nowv0 do begin dfs(childnowv); inc(yesv,nochildnowv); inc(nov,max(yeschildnowv,nochildnowv); nowv:=prenowv; end; end;begin read(n); for i:=1 to n do read(yesi); fillchar(pres,sizeof(pres),1); root:=n*(n+1) div 2; for i:=1 to n-1 do begin read(x,y); childi:=x; prei:=nowy; nowy:=i; if presx then begin dec(root,x); presx:=false; end; end; dfs(root); writeln(max(yesroot,noroot);end.戰(zhàn)略游戲(普通樹，無根樹DP，形態(tài)無關(guān))ProblemBob喜歡玩電腦游戲，特別是戰(zhàn)略游戲。但是他經(jīng)常無法找到快速玩過游戲的辦法?，F(xiàn)在他有個問題。他要建立一個古城堡，城堡中的路形成一棵樹。他要在這棵樹的結(jié)點上放置最少數(shù)目的士兵，使得這些士兵能了望到所有的路。注意，某個士兵在一個結(jié)點上時，與該結(jié)點相連的所有邊將都可以被了望到。請你編一程序，給定一樹，幫Bob計算出他需要放置最少的士兵.Input第一行為一整數(shù)，表示有組測試數(shù)據(jù)每組測試數(shù)據(jù)表示一棵樹，描述如下：第一行 N，表示樹中結(jié)點的數(shù)目。第二行至第N+1行，每行描述每個結(jié)點信息，依次為：該結(jié)點標(biāo)號i，k(后面有k條邊與結(jié)點I相連)。接下來k個數(shù)，分別是每條邊的另一個結(jié)點標(biāo)號r1，r2，.，rk。 對于一個n(0n=1500)個結(jié)點的樹，結(jié)點標(biāo)號在0到n-1之間，在輸入數(shù)據(jù)中每條邊只出現(xiàn)一次。 Output輸出文件僅包含一個數(shù)，為所求的最少的士兵數(shù)目。 例如，對于如下圖所示的樹： 答案為1（只要一個士兵在結(jié)點1上）。 Sample Input240 1 11 2 2 32 03 053 3 1 4 21 1 02 00 04 0Sample Output12這道題目是一個經(jīng)典的問題，來源于同濟大學(xué)的OJ。是一顆無根樹的題目，而且結(jié)果和樹的形態(tài)沒有關(guān)系分析可見,對于當(dāng)前結(jié)點i,它有num個子結(jié)點,它有它有3種狀態(tài):1:在當(dāng)前位放置守衛(wèi)的情況(被自己所控制)2:不在當(dāng)前位放置守衛(wèi),但是它已經(jīng)被它的子結(jié)點所控制3:不在當(dāng)前位放置守衛(wèi),它還沒有被它的子結(jié)點所影響(即被其父結(jié)點控制)用fi,x表示結(jié)點i的第x種情況:1情況的值由其子結(jié)點的1,2,3情況得到最優(yōu)2情況的值由其子結(jié)點的1,2情況得到最優(yōu)3情況的值只可由其2情況求和.第2種情況要特別注意,要求它的子結(jié)點中必須有一個是1狀況的,所以可以先將最小值求和,然后加上這num個子結(jié)點中每個的1情況與最優(yōu)情況的f值之差-most方程:fi,1:=(minfsonj,1,fsonj,2,fsonj,3)+aifi,2:=(minfsonj,1,fsonj,2)+mostfi,3:=(fsonj,2), 1=j=num還有要注意的一點就是對于極限數(shù)據(jù),樹被拉成了一條鏈.有向圖解法如果每次遞歸都開一個數(shù)組那么內(nèi)存會爆,對此,可以不用數(shù)組記錄子結(jié)點,而直接用鏈表就可以大大節(jié)約空間了.甚至把數(shù)組改成全局變量也是可行的,就是注意遞歸調(diào)用要在DP之前.代碼#include #define MAXN 1501#define MAXINT 2000000000typedef struct int v, num; int childMAXN;node;node aMAXN;int fMAXN4;int min2(int x, int y) return xy?x:y;int min3(int x, int y, int z) return min2(x, min2(y, z);void dp(int i) int j, k,a2; if (ai.num = 0) fi1 = ai.v; fi2 = ai.v; return; fi2 = ai.v; for (j = 1; j = ai.num; j+) dp(ai.childj); fi2 += min3(fai.childj1, fai.childj2, fai.childj3); fi3 += fai.childj1; fi1 = MAXINT; for (j = 1; j = ai.num; j+) a2 = fai.childj2; for (k = 1; k = ai.num; k+) if (j != k) if (aai.childk.num != 0) a2 += min2(fai.childk2, fai.childk1); else a2 += fai.childk2; if (a2 fi1) fi1 = a2; int main() int i, j, m, n, p, r, root; m = MAXINT; r = 0; root = 0; scanf(%d, &n); for (i = 1; i = n; i+) scanf(%d, &p); scanf(%d%d, &ap.v, &ap.num); r += p; for (j = 1; j fs2fs3fsn，則我們讓root在每個單位時間內(nèi)依次通知s1,s2,s3.sn,得到的結(jié)果是最優(yōu)的。也就是froot=maxfsi+i.也就是說哪個兒子的f值最大我們先通知誰。這個是看起來很顯然的結(jié)論。但是我們需要證明它。簡略證明如下：假設(shè)root的兒子為s1,s2,s3,sn,且fs1fs2fs3fsn.則我們要證明：froot=maxfsi+i是最優(yōu)的。我們把通知兒子的次序中任意交換兩個。即原來有 ifsj.，通知這兩顆子樹的最短時間是 minfsi+i,fsj+j；當(dāng)交換順序以后，則通知這兩個子樹的最短時間是Minfsi+j,fsj+i,因為 fsifsj 且 ji, 則我們交換順序后的到的最小值顯然不會比原來的最優(yōu)值更優(yōu)。因此算法得到證明。由此得到了我們的主算法：枚舉每個節(jié)點當(dāng)作樹根，建立無根樹。每次進行一次樹形動態(tài)規(guī)劃，方程為fi=maxfsj+j 其中sj是i的兒子。這個題目的特點就是最優(yōu)值和樹的形態(tài)是有關(guān)系的，而這個樹是一個無根樹，所以需要去枚舉節(jié)點作為樹根的情況才可以確定最優(yōu)解。#include #include #include #include using namespace std;const int maxn=1024;int resmaxn;struct edge int y; edge* next; edge(int y,edge* next): y(y),next(next)*Emaxn;int root;int parmaxn;int ordermaxn;int costmaxn;int best;int N;void input() scanf(%d,&N); memset(E,0,sizeof(E); for(int i=2;inext) int y=e-y; if(y=parx)continue; pary=x; ordertail+=y; if(head=tail)break; int compare(const void* a,const void* b) return *(int*)a-*(int*)b;int childmaxn;void handle(int x) int childn=0; for(edge* e=Ex;e;e=e-next) int y=e-y; if(y=parx)continue; childchildn+=costy; qsort(child,childn,sizeof(int),compare); costx=0; for(int i=0;icostx) costx=cur; int solve(int x) root=x; bfs(); for(int i=N-1;i=0;-i) handle(orderi); if(costorderibest) return INT_MAX; return costroot;void solve() best=INT_MAX; for(int i=1;i=N;+i) root=i; resi=solve(i); if(resibest) best=resi; void output() printf(%dn,best+1); bool first=true; for(int i=1;i=N;+i) if(resi=best) if(first) first=false; else putchar( ); printf(%d,i); putchar(n);int main() freopen(badnews.in,r,stdin); freopen(badnews.out,w,stdout); input(); solve(); output();Tree-dp技巧：多叉樹轉(zhuǎn)二叉樹選課 問題描述在大學(xué)里每個學(xué)生，為了達到一定的學(xué)分，必須從很多課程里選擇一些課程來學(xué)習(xí)，在課程里有些課程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之前學(xué)習(xí)?，F(xiàn)在有N門功課，每門課有個學(xué)分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學(xué)完了課程a，才能學(xué)習(xí)課程b）。一個學(xué)生要從這些課程里選擇M門課程學(xué)習(xí)，問他能獲得的最大學(xué)分是多少？輸入：第一行有兩個整數(shù)N,M用空格隔開。(1=N=200,1=M=150)接下來的N行,第I+1行包含兩個整數(shù)ki和si, ki表示第I門課的直接先修課，si表示第I門課的學(xué)分。若ki=0表示沒有直接先修課（1=ki=N, 1=si=0 then exit; treedp(ax.r,y);只有右子樹的情況 j:=bax.r,y; for k:=1 to y do左右子樹都有的情況 begin treedp(ax.l,k-1); treedp(ax.r,y-k); i:=bax.l,k-1+bax.r,y-k+ax.k; if ij then j:=i; end; bx,y:=j; end;beginreadln(s);assign(input,s);reset(input);readln(n,m);fillchar(f,sizeof(f),0);for i:=0 to n do begin ai.l:=-1;ai.r:=-1;ai.k:=-1;end;build treefor i:=1 to n do begin readln(k,l); ai.k:=l; if fk=0 then ak.l:=i else afk.r:=i; fk:=i; end;bianjiefor i:=-1 to n do for j:=-1 to m do if (i=-1) or (j=0) then bi,j:=0 else bi,j:=-1;tree dptreedp(a0.l,m);outputwriteln(ba0.l,m);end.Tree-dp與其他算法的結(jié)合pku1947（DP+背包）Rebuilding RoadsDescriptionThe cows have reconstructed Farmer Johns farm, with its N barns (1 = N = 150, number 1.N) after the terrible earthquake last May. The cows didnt have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree. Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 = P = N) barns from the rest of the barns.Input* Line 1: Two integers, N and P * Lines 2.N: N-1 lines, each with two integers I and J. Node I is node Js parent in the tree of roads. OutputA single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated. Sample Input11 61 21 31 41 52 62 72 84 94 104 11Sample Output2HintA subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed. SourceUSACO 2002 February題目大意：題目大意是給一棵樹，要去掉最少的邊，使一棵子樹從中分離出來，且這棵子樹要恰有B個節(jié)點。fx，i(1 = i = p)表示以x為根的子樹，變成剩下i個點的子樹，且剩余子樹包含根結(jié)點，需要去掉的最少邊數(shù)。那么父結(jié)點的f值可以由它所有的兒子的f值做背包得到。最后的答案是min(min(fi，p) + 1 (2 = i b then exit(b); exit(a);end;procedure init;begin readln(n,p); for i:=1 to n-1 do begin readln(t1,t2); inc(ct1);inc(ct2); mapt1,ct1:=t2; mapt2,ct2:=t1; end; fillchar(used,sizeof(used),false); for i:=1 to n do for j:=0 to n do fi,j:=maxint;end;procedure dfs(now,father:integer);var i,j,k:longint;begin usednow:=true; for i:=1 to cnow do if (mapnow,ifather) and (not(usedmapnow,i) then dfs(mapnow,i,now); fnow,1:=cnow; for i:=1 to cnow do for k:=p-1 downto 0 do if fnow,kmaxint then for j:=1 to p do if fmapnow,i,jmaxint then fnow,k+j:=min(fnow,k+j,(fmapnow,i,j+fnow,k-2);end;procedure print;begin ans:=maxint; for i:=2 to n do ans:=min(ans,fi,p); ans:=min(ans,f1,p); writeln(ans);end;begin init; dfs(1,0); print;end.加分二叉樹（二叉樹DP，也可理解為類石子合并的線性結(jié)構(gòu)）【問題描述】 設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點編號。每個節(jié)點都有一個分?jǐn)?shù)（均為正整數(shù)），記第i個節(jié)點的分?jǐn)?shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下： subtree的左子樹的加分 subtree的右子樹的加分subtree的根的分?jǐn)?shù) 若某個子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分?jǐn)?shù)。不考慮它的空子樹。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree。要求輸出； （1）tree的最高加分 （2）tree的前序遍歷【輸入格式】 第1行：一個整數(shù)n（n30），為節(jié)點個數(shù)。 第2行：n個用空格隔開的整數(shù)，為每個節(jié)點的分?jǐn)?shù)（分?jǐn)?shù)100）?！据敵龈袷健?第1行：一個整數(shù)，為最高加分（結(jié)果不會超過4,000,000,000）。 第2行：n個用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永?5 5 7 1 2 10【輸出樣例】 145 3 1 2 4 5valuei,j表示從節(jié)點i到節(jié)點j所組成的二叉樹的最大加分，則動態(tài)方程可以表示如下：valuei,j=maxvaluei,i+valuei+1,j,valuei+1,i+1+valuei,i*valuei+2,j, valuei+2,i+2+valuei,i+1*valuei+3,j,valuej-1,j-1+valuei,j-2*valuej,j, valuej,j+valuei,j-1題目還要求輸出最大加分樹的前序遍歷序列，因此必須在計算過程中記下從節(jié)點i到節(jié)點j所組成的最大加分二叉樹的根節(jié)點，用數(shù)組rooti,j表示PASCAL源程序$N+program NOIP2003_3_Tree; const maxn=30; var i,j,n,d:byte; a:array1.maxnof byte; value:array1.maxn,1.maxnof comp; root:array1.maxn,1.maxnof byte; s,temp:comp; f1,f2:text;fn1,fn2,fileNo:string; procedure preorder(p1,p2:byte);按前序遍歷輸出最大加分二叉樹 begin if p2=p1 then begin write(f2,rootp1,p2, ); preorder(p1,rootp1,p2-1); preorder(rootp1,p2+1,p2); end; end; begin write(Input fileNo:);readln(fileNo); fn1:=tree.in+fileNo;fn2:=tree.ou+fileNo; assign(f1,fn1);reset(f1); assign(f2,fn2);rewrite(f2); readln(f1,n); for i:=1 to n do read(f1,ai); close(f1); fillchar(value,sizeof(value),0); for i:=1 to n do begin valuei,i:=ai;計算單個節(jié)點構(gòu)成的二叉樹的加分 rooti,i:=i;記錄單個節(jié)點構(gòu)成的二叉樹的根節(jié)點 end; for i:=1 to n-1 do begin valuei,i+1:=ai+ai+1;計算相鄰兩個節(jié)點構(gòu)成的二叉樹的最大加分 rooti,i+1:=i;記錄相鄰兩個節(jié)點構(gòu)成的二叉樹的根節(jié)點；需要說明的是，兩個節(jié)點構(gòu)成的二叉樹，其根節(jié)點可以是其中的任何一個；這里選編號小的為根節(jié)點，則編號大的為其右子樹；若選編號大的為根節(jié)點，則編號小的為其左子樹；因此，最后輸出的前序遍歷結(jié)果會有部分不同，但同樣是正確的。如果最大加分二叉樹的所有節(jié)點的度數(shù)都是0或2，則最后輸出的前序遍歷結(jié)果是唯一的。 end; for d:=2 to n-1 do begin依次計算間距為d的兩個節(jié)點構(gòu)成的二叉樹的最大加分 for i:=1 to n-d do begin s:=valuei,i+valuei+1,i+d;計算以i為根節(jié)點，以i+1至i+d間所有節(jié)點為右子樹的二叉樹的最大加分 rooti,i+d:=i; 記錄根節(jié)點i for j:=1 to d do begin temp:=valuei+j,i+j+valuei,i+j-1*valuei+j+1,i+d;計算以i+j為根節(jié)點，以i至i+j-1間所有節(jié)點為左子樹，以i+j+1至i+d間所有節(jié)點為右子樹的二叉樹的最大加分 if temps then begin如果此值為最大 s:=temp;rooti,i+d:=i+j;記下新的最大值和新的根節(jié)點 end; end; temp:=valuei,i+d-1+valuei+d,i+d;計算以i+d為根節(jié)點，以i至i+d-1間所有節(jié)點為左子樹的二叉樹的最大加分 if temps then begin s:=temp;rooti,i+d:=i+d+1; end; va