樹形DP之個人整理總結(jié)

樹形DP 第頁 Auther:陳江勇2008年10月22日樹形DP二叉蘋果樹(ural1108)題目意思：有一棵蘋果樹，蘋果樹的是一棵二叉樹，共N個節(jié)點，樹節(jié)點編號為1~N，編號為1的節(jié)點為樹根，邊可理解為樹的分枝，每個分支都長著若干個蘋果，現(xiàn)在要要求減去若干個分支，保留M個分支，要求這M個分支的蘋果數(shù)量最多。輸入：NM接下來的N-1行是樹的邊，和該邊的蘋果數(shù)NandM(1≤M<N;1<N≤100)輸出：剩余蘋果的最大數(shù)量。input52131141023203520output21算法：刪除了某個分支，那么這個分支下的子分支也同時刪除。保留M個分支，也就是刪除N-M-1個分支。剩余的最多蘋果數(shù)=總蘋果數(shù)-剪掉的蘋果數(shù)。注意本題給的邊并沒有按照樹根--樹葉的形式來給，也沒有按照樹的順序給出邊。本來想一個節(jié)點對應(yīng)一個分支長著的蘋果數(shù)量，cost[v]就表示v這個節(jié)點的蘋果數(shù)，可以這樣做，但是在輸入的時候，不知道這個蘋果數(shù)量是那個節(jié)點的，因為不知道哪個是哪個的子結(jié)點。所以用了無向圖和蘋果數(shù)加到邊上去。我的解法中：這題的樹狀DP的整體思想個pku3345是一樣的。有一些不一樣的地方要注意一下：本程序其實不僅僅針對二叉樹，可以是任意的樹，刪除任意個分支都有算。#include<iostream>#include<vector>#include<limits>usingnamespacestd;#defineMN110intf[2*MN],p[MN],tmp[MN];intN,M;boolvisit[MN];structNODE{ intval; intcost;};vector<NODE>G[MN];inlineintmax(inta,intb){ returna>b?a:b;}inlineintmin(inta,intb){ returna<b?a:b;}voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); } memset(visit,false,sizeof(visit));}intDP(intv,intfrom){ visit[v]=true; inti,j,k,s,w,last,now; s=G[v].size(); if(s==1)//這邊不再是s==0 { p[0]=0; return1; } last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i].val; if(visit[w]==true) continue; now=DP(w,from+last+1); p[now]=p[now-1]+G[v][i].cost;//這邊不要漏,把節(jié)點w也給刪除 for(j=0;j<=last+now;j++) tmp[j]=INT_MAX; for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { tmp[j+k]=min(tmp[j+k],f[from+j]+p[k]); } } last+=now; for(j=0;j<=last;j++) { f[from+j]=tmp[j]; } } for(i=0;i<=last;i++) p[i]=f[i+from]; last++;//加上自身節(jié)點 returnlast;}intmain(){ inti,a,b,sum,c; NODEtmp; while(scanf("%d%d",&N,&M)!=EOF) { sum=0; my_clear(); for(i=1;i<N;i++) { scanf("%d%d%d",&a,&b,&c); tmp.cost=c; tmp.val=b; G[a].push_back(tmp); tmp.val=a; G[b].push_back(tmp); sum+=c; } DP(1,0); printf("%d\n",sum-f[N-M-1]); } return0;}有限電視網(wǎng)絡(luò)（pku1155TELE）題目描述：有一個電視臺要用電視網(wǎng)絡(luò)轉(zhuǎn)播節(jié)目。這種電視網(wǎng)絡(luò)是一樹，樹的節(jié)點為中轉(zhuǎn)站或者用戶。樹節(jié)點的編號為1~N,其中1為總站，2~(N-M)為中轉(zhuǎn)站，（總站和中轉(zhuǎn)站統(tǒng)稱為轉(zhuǎn)發(fā)站）N-M+1~N為用戶，電視節(jié)目從一個地方傳到另一個地方都要費用，同時每一個用戶愿意出相應(yīng)的錢來付電視節(jié)目?，F(xiàn)在的問題是，在電視臺不虧本的前提下，要你求最多允許有多少個用戶可以看到電視節(jié)目。輸入：NMN表示轉(zhuǎn)發(fā)站和用戶總數(shù)，M為用戶數(shù)以下N-M行，第i行第一個K，表示轉(zhuǎn)發(fā)站i和K個（轉(zhuǎn)發(fā)站或用戶）相連,其后第j對數(shù)val,cost表示，第i個轉(zhuǎn)發(fā)站到val有邊，費用cost.最后一行M個數(shù)表示每個用戶愿意負的錢。輸出：不虧本前提下，可以收到節(jié)目最多的用戶數(shù)。（如果某個用戶要收到節(jié)目（葉子結(jié)點），那么電視臺到該用戶的路徑節(jié)點的費用都要付）SampleInput963223293242523627282433311SampleOutput5算法：這是一道樹狀態(tài)DP.狀態(tài)f(n,k)表示第n個節(jié)點發(fā)送給k個用戶最多能盈利多少，k不超過n所管轄的葉節(jié)點個數(shù)。那么答案就是使f(root,k)>=0最大的k了。通常我們狀態(tài)轉(zhuǎn)移的時候是枚舉每個子狀態(tài)的，但是這里我們還得用一個DP來枚舉子狀態(tài)。假設(shè)一個節(jié)點i有n個子節(jié)點，那么求f(i,k)時就要考慮怎么把k分到n個節(jié)點上使得盈利最大。下面關(guān)鍵是如何去枚舉：如果節(jié)點i有X個子結(jié)點設(shè)為1~~X，假如當(dāng)前DP算到第j（0=<j<=X）個節(jié)點,第j個節(jié)點有now個用戶,而0~j-1共有l(wèi)ast用戶，f[i][k]=max(f[i][k],f[i][a]+f[j][b])(其中a+b=k,0=<k<=last+now);f[i][a]表示把a個用戶分配給0~~j-1節(jié)點，分配b個用戶給j這個節(jié)點。本程序用寫了另外一個用滾動數(shù)組來省空間的方法，注意多了一個參數(shù)from,否則原來的值會被覆蓋掉。#include<iostream>#include<limits>#include<vector>usingnamespacestd;intN,M;vector<int>G[3001];intmoney[3001],cost[3001],p[3001],f[6001],tmp[3001];voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); }}intDP(intv,intfrom){ inti,s,last,now,k,j,w; s=G[v].size(); if(!s) { p[0]=0; p[1]=money[v-N+M]; return1; } last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i]; now=DP(w,from+last+1); for(j=0;j<=last+now;j++) { tmp[j]=INT_MIN; } for(j=1;j<=now;j++) { p[j]-=cost[w]; } for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { if(f[from+j]+p[k]>tmp[j+k]) { tmp[j+k]=f[from+j]+p[k]; } } } tmp[0]=0; last+=now; for(j=0;j<=last;j++) { f[j+from]=tmp[j]; } }/* printf("%d\n",v); for(i=0;i<=last;i++) { printf("%d%d\n",i,f[i+from]); }*/ for(j=0;j<=last;j++) p[j]=f[j+from]; returnlast;}intmain(){ inti,K,j,b; scanf("%d%d",&N,&M); my_clear(); for(i=1;i<=N-M;i++) { scanf("%d",&K); for(j=0;j<K;j++) { scanf("%d",&b); scanf("%d",&cost[b]); G[i].push_back(b); } } for(i=1;i<=M;i++) scanf("%d",&money[i]); DP(1,0); for(i=M;i>=0;i--) { if(f[i]>=0) break; } printf("%d\n",i); return0;}最少步數(shù)摘最多的蘋果(pku2486AppleTree)DescriptionWshxztisalovelygirl.Shelikesappleverymuch.OnedayHXtakeshertoanappletree.ThereareNnodesinthetree.Eachnodehasanamountofapples.Wshxztstartsherhappytripatonenode.Shecaneatupalltheapplesinthenodesshereaches.HXisakindguy.Heknowsthateatingtoomanycanmakethelovelygirlbecomefat.Sohedoesn’tallowWshxzttogomorethanKstepsinthetree.Itcostsonestepwhenshegoesfromonenodetoanotheradjacentnode.Wshxztlikesappleverymuch.Soshewantstoeatasmanyasshecan.CanyoutellhowmanyapplesshecaneatinatmostKsteps.InputThereareseveraltestcasesintheinputEachtestcasecontainsthreeparts.ThefirstpartistwonumbersNK,whosemeaningswehavetalkedaboutjustnow.Wedenotethenodesby12...N.Sinceitisatree,eachnodecanreachanyotherinonlyoneroute.(1<=N<=100,0<=K<=200)ThesecondpartcontainsNintegers(Allintegersarenonnegativeandnotbiggerthan1000).TheithnumberistheamountofapplesinNodei.ThethirdpartcontainsN-1line.TherearetwonumbersA,Bineachline,meaningthatNodeAandNodeBareadjacent.Inputwillbeendedbytheendoffile.Note:WshxztstartsatNode1.OutputForeachtestcase,outputthemaximalnumbersofapplesWshxztcaneatataline.SampleInput2101112320121213SampleOutput112f[i][j][0]保存對于節(jié)點i向其子樹走j步(可能有點重復(fù))摘到的最多蘋果數(shù)f[i][j][1]保存對于節(jié)點i向其子樹走j步并且返回到i節(jié)點摘到的最多蘋果數(shù)對于葉節(jié)點f[i][0][0/1]=apNum[i];對于其它節(jié)點f[i][j][0]=max{j-2*p-1步，其中p個子樹返回,1個子樹不需要返回,所得到最多蘋果數(shù),p不定}；f[i][j][1]=max{j-2*p步，p個子樹都返回,所得到的最多蘋果數(shù),p不定}這兩步中間過程都需要DP復(fù)雜度=j*子樹個數(shù)(<n)那么最終結(jié)果就是f[1][k][0]整個大的DP時間復(fù)雜度<n*(k*n)<2*10^6樹型DP中套小DP*/#include<iostream>#include<vector>usingnamespacestd;#defineMN101intback[201][201],go[201][201],num[101],t1[201],t2[201];vector<int>G[MN];intN,K;inlineintmax(inta,intb){ returna>b?a:b;}voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); } memset(go,0,sizeof(go)); memset(back,0,sizeof(back));}voidDP(intv,intp){ inti,s,w,j,m,n; s=G[v].size(); for(i=0;i<s;i++) { w=G[v][i]; if(w==p) continue; DP(w,v); back[w][0]=0; back[w][1]=0; go[w][0]=0; for(j=K;j>=2;j--) { back[w][j]=back[w][j-2]+num[w]; } for(j=K;j>=1;j--) { go[w][j]=go[w][j-1]+num[w]; } memset(t1,0,sizeof(t1)); memset(t2,0,sizeof(t2)); for(m=0;m<=K;m++) { for(n=0;n<=m;n++) { t1[m]=max(t1[m],back[v][n]+back[w][m-n]); t2[m]=max(t2[m],max(go[v][n]+back[w][m-n],back[v][n]+go[w][m-n])); } } for(j=0;j<=K;j++) { back[v][j]=t1[j]; go[v][j]=t2[j]; } }}intmain(){ inta,b; while(scanf("%d%d",&N,&K)!=EOF) { inti; for(i=1;i<=N;i++) scanf("%d",&num[i]); my_clear(); for(i=1;i<N;i++) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } DP(1,0); intans=max(go[1][K],back[1][K]); ans+=num[1]; printf("%d\n",ans); } return0;}鉆石總統(tǒng)(pku3345BribingFIPA)題目大意：有個人要競選某職務(wù),有N個國家參選，他想通過賄賂某些國家來贏得這個國家的選票，每個國家都要花費相應(yīng)的鉆石才可以被賄賂。因為國家與國家之間存在著控制關(guān)系，付費給某個國家，那么就可以贏得這個國家和它直接或間接控制的所有國家的選票。其實國家的控制關(guān)系可以看成一棵樹，對于本題，是給一個森林。你的任務(wù)是如果至少要贏得M個國家的選票，最少要花多少鉆石。輸入：32//N,M接下來是N行，每行前兩個為國家名和賄賂改國家需要的鉆石數(shù)，后面跟著的是這個國家可以控制的國家名字，可以沒有。Aland10Boland20AlandColand15#輸出：最后需要的鉆石數(shù)。輸入處理用了sstream，真的很好用。不然可能很不好處理。這題要注意：輸入不會有環(huán)。但是給你的數(shù)可能不聯(lián)通，所以加一個根節(jié)點吧所有的樹都連成一棵樹，然后在書上進行DP.DP的方法和1155的方法類似，也用了from參數(shù)。#include<iostream>#include<vector>#include<map>#include<limits>#include<sstream>usingnamespacestd;map<string,int>mp;#defineMN210vector<int>G[MN];intf[2*MN],p[MN],tmp[MN],cost[MN],in[MN];intN,M;charchartmp[1000];inlineintmax(inta,intb){ returna>b?a:b;}inlineintmin(inta,intb){ returna<b?a:b;}voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); } memset(in,0,sizeof(in)); mp.clear();}intDP(intv,intfrom){ inti,j,k,s,w,last,now; s=G[v].size(); if(s==0) { p[0]=0; p[1]=cost[v]; return1; } last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i]; now=DP(w,from+last+1); for(j=0;j<=last+now;j++) tmp[j]=INT_MAX; for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { tmp[j+k]=min(tmp[j+k],f[from+j]+p[k]); } } last+=now; for(j=0;j<=last;j++) { f[from+j]=tmp[j]; } } f[from+last+1]=cost[v]; last++; for(i=0;i<=last;i++) p[i]=f[i+from]; returnlast;}intmain(){ inti,root,a,b,id; stringt; while(gets(chartmp)) { if(chartmp[0]==0) continue; if(chartmp[0]=='#') break; stringstreamss(chartmp); ss>>N>>M; id=1; my_clear(); for(i=1;i<=N;i++) { scanf("%s",chartmp); if((a=mp[chartmp])==0) { a=mp[chartmp]=id++; } scanf("%d",&cost[a]); gets(chartmp); stringstreamss(chartmp); while(ss>>t) { if((b=mp[t])==0) { b=mp[t]=id++; } in[b]++;// G[a].push_back(b);//這兩個是放在if外，開始的時候錯了 } } for(i=1;i<=N;i++) { if(in[i]==0) { G[0].push_back(i); } } cost[0]=0; inttt=DP(0,0); intans=INT_MAX; for(i=M;i<=N;i++) { if(ans>f[i]) { ans=f[i]; } } printf("%d\n",ans); } return0;}刪除最少的邊使得樹剩下的給定數(shù)目節(jié)點(pku1947RebuildingRoads)題目的意思：給你一棵樹，求通過求通過刪除最少的邊，使得剩余子樹有給定的節(jié)點數(shù)。輸入：N,P//N為節(jié)點總數(shù)，P為刪除邊后剩余的節(jié)點樹以下N-1行給出樹的邊。題目沒說清楚給出的邊是否是有向的。對于本題可以按照有向樹來做，其實無向樹來做更保險，應(yīng)用性更廣。看成有向樹，對于本題樹根就是1，題目沒說，判斷一下更保險，如果是看成無向樹，則無所謂誰為根節(jié)點。開始的時候，對于本題一直按照以往的樹形DP的方法來做，一直錯。查了好久才查出哪里錯了，因為看到別人的程序的一個地方，多了一段程序，刪除這一部分則是錯誤的。ans=f[root][p];for(i=1;i<=n;i++)//這個for循環(huán)是必須的。{if(f[i][p]<ans)ans=f[i][p]+1;//這邊之所以要加一因為要刪除i節(jié)點和其父親節(jié)點的連接}后來我就在DP的函數(shù)末尾，多了一個判斷。按照以往的DP方法，一下這個例子是錯的，輸出的是3，而答案是11271111121223244548565789810如果看成有向樹,1為根，以1為根進行DP的最后的答案是3，原因是這樣DP的所有結(jié)果(即剩余的P個節(jié)點)都包含根節(jié)點1,而對于上面一個數(shù)據(jù)，一最后的節(jié)點不包含根根節(jié)點，而是刪除一個邊后，邊下面的子樹保留，上面的部分（包括根節(jié)點全部刪除），所以就多了判斷那一部分。即在DP的子問題中判斷是否有更優(yōu)解。#include<iostream>#include<vector>usingnamespacestd;#defineMN160vector<int>G[MN];intf[2*MN],p[MN],tmp[MN],N,P,in[MN],root;intans;voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); }}inlineintmin(inta,intb){ returna<b?a:b;}intDP(intv,intfrom){ intlast,now,w,i,s,j,k; s=G[v].size(); last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i]; now=DP(w,last+from+1); for(j=0;j<=last+now;j++) { tmp[j]=INT_MAX; } for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { tmp[j+k]=min(tmp[j+k],f[j+from]+p[k]); } } last+=now; for(j=0;j<=last;j++) { f[j+from]=tmp[j]; } } p[0]=0; for(j=0;j<=last;j++) p[j]=f[j+from]; last++; p[last]=0; if(last>=P&&v!=root&&p[last-P]+1<ans) { ans=p[last-P]+1; } p[last]=1; returnlast;}intmain(){ inti,a,b; while(scanf("%d%d",&N,&P)!=EOF) { my_clear(); ans=INT_MAX; memset(in,0,sizeof(in)); for(i=1;i<N;i++) {//對于本題可以按照有向樹來做，其實無向樹來做更保險，應(yīng)用性更廣?？闯捎邢驑?，對于本題樹根就是1， scanf("%d%d",&a,&b);//為了保險，還是要判斷。 G[a].push_back(b); in[b]++; } for(i=1;i<=N;i++) if(!in[i]){ root=i; break; } DP(root,0); if(f[N-P]<ans) ans=f[N-P]; printf("%d\n",ans); } return0;}/*1271111121223244548565789810這組數(shù)據(jù)輸出為1*/樹的中心(ural_1056Computernet)什么樹的中心？樹：無根樹某個節(jié)點的P值：到所有節(jié)點的距離的最大值中心：P值最小的那個1.一棵樹，或者有一個中心，或者有兩個，但至少有一個我的做法用了下面結(jié)論：結(jié)論一：中心一定在任意一個深度最大的節(jié)點到根節(jié)點的路徑上（如果有多個深度最大的點就在路徑的交集上）結(jié)論二：中心在樹上的最長的路徑上（有多條就在交集上）所以只要任意找出一個深度最大的點，求出其它點到它的距離的最大值，順著到根的路徑就能把中心找出來了，如果最大值是奇數(shù)就有兩個中心，偶數(shù)就有一個中心以下這兩種解法沒經(jīng)過證明：1.不斷的剝掉葉子，用個數(shù)組記錄葉子，剝掉葉子后立即檢查這個葉子的父親，如果他父親的度是1，則把他放到數(shù)組里，要小心只剩下2個點的時候，那時2個點就是中心了2.由于是樹結(jié)構(gòu)，所以可以把一棵樹看成這樣：(t1)(t2)一條邊ei(u,v)把一棵樹分成2部分，如果t1的深度>t2的，則中心在t1,若小于就在t2,如果相等就是u,v2點.這樣只需要O(E),不過寫的時候注意一點才行讀入的時候用個par[i]記錄i的父親是誰,順便連度數(shù)也記錄了讀完后,第一次把葉子找出來,這樣delete那些葉子，檢查他們的父親，新的葉子一定在他們的父親中產(chǎn)生，這樣繼續(xù)delete以下代碼是根據(jù)結(jié)論來做，還有一個是用樹狀DP.#include<iostream>#include<vector>usingnamespacestd;#defineMN10010vector<int>G[MN];intN,par[MN];booltag[MN],visit[MN],two,finish;intd[MN],depmax,vmax,lans[2],tn;voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); }}voidbuild(){ scanf("%d",&N); inti,b; my_clear(); for(i=1;i<N;i++) { scanf("%d",&b); G[b].push_back(i+1); G[i+1].push_back(b); }}voiddfs(intv,intfather,intdep){ inti,s,w; par[v]=father; d[v]=dep; visit[v]=true; if(dep>depmax) { depmax=dep; vmax=v; } s=G[v].size(); for(i=0;i<s;i++) { w=G[v][i]; if(!visit[w]) { dfs(w,v,dep+1); } }}voidswap(int*ans){ intt=ans[0]; ans[0]=ans[1]; ans[1]=t;}voidsolve(){ intv,i; memset(visit,false,sizeof(visit)); depmax=-1; dfs(1,-1,0); memset(visit,false,sizeof(visit)); depmax=-1;//depmax要重新清0，這點不要漏 dfs(vmax,-1,0); intk=depmax/2; intans[2]={-1,-1}; v=vmax; for(i=1;i<=k;i++) { v=par[v]; } ans[0]=v; if(N!=1&&depmax%2==1) { ans[1]=par[v]; } printf("%d",ans[0]); if(ans[1]!=-1) printf("%d",ans[1]); printf("\n");}intmain(){ build(); solve(); return0;}以下是用樹狀DP來做.枚舉每個點，然后DFS復(fù)雜度O(N2)，超時是顯然的事情?？梢园l(fā)現(xiàn)其實有很多DFS都重復(fù)做了同樣的工作，產(chǎn)生了浪費，所以應(yīng)該選擇動態(tài)規(guī)劃解決這個問題。樹上的動規(guī)，是否直接可以寫出下面的狀態(tài)轉(zhuǎn)移方城呢？f[i]:=max(f[son],f[father])+1廢話，顯然是不行的，son和father的值不可能同時得到。但是不要放棄，解決這個沖突的方法，就是采用二次動規(guī)。第一次動規(guī)做f[i]:=max(f[son])+1，第二次動規(guī)做f[i]:=max(f[i],f[father]+1)。但是存在一個問題就是如果f[father]的值是從i那里得到的，這樣計算顯然就錯了。不要放棄，在實際操作過程中，f需要記下兩個值，一個是最優(yōu)值，一個是次優(yōu)值，這兩個值必須由不用的子結(jié)點得到。這樣當(dāng)最優(yōu)值發(fā)生矛盾的時候，次優(yōu)值一定不會矛盾。問題就解決了。復(fù)雜度O(N)十分的理想。剛開始看到這個解題報告不知道什么時候矛盾，其實這邊說的不是很明白。1.做一次dfs,第一次算出每一個節(jié)點的第一大和二大的深度d[i][0],d[i][1]，并記錄兩個深度的值是從哪個子節(jié)點得來的f1[],f2[]，在算的過程并記錄每一個節(jié)點的父親節(jié)點p[w]。2.第二次dfs,在第一次dfs的基礎(chǔ)上，算出每個節(jié)點v到從父親節(jié)點走所有節(jié)點（不包括v的子節(jié)點）的最大距離存于maxd[w]中，maxd[w]={maxd[p[w]]+1,或d[p[w]][0或1]+1}。3.最后maxd[i]=max(maxd[i],d[i][0]);就是節(jié)點i到所有節(jié)點的最大距離。但是對于本題，其實可以不用做dfs，因為這個樹的很特別，節(jié)點的連接是按順序，所以可以不用dfs，直接用迭代就可以解決了。（見后面的pascal程序）其實上面的第二次dfs也可以不用，在第一次dfs的時候，記錄節(jié)點dfs的編號，然后就可以用迭代了。本題也可以出個變形的題目，求出每一個節(jié)點的到所有節(jié)點的最大距離，時間復(fù)雜度O(n);其實本題就是求樹的中心。程序調(diào)了很久，開始的時候出現(xiàn)很多錯誤。#include<iostream>#include<vector>usingnamespacestd;#defineMN10010intd[MN][2],N,up[MN],p[MN],f1[MN],f2[MN],maxd[MN];boolvisit[MN];vector<int>G[MN];intdfs(intv){ inti,s,t,w; visit[v]=true; s=G[v].size();/* if(s==1)//這邊錯了，根節(jié)點也可能s==1，不一定就是葉子節(jié)點 { d[v][0]=0; return0; }*/ d[v][0]=d[v][1]=0;//多這一個 for(i=0;i<s;i++) { w=G[v][i]; if(!visit[w]) { p[w]=v; t=dfs(w)+1; if(t>d[v][0]) { d[v][1]=d[v][0];//開始時少了這一個句,開始的時候后這一句放在下面一句的下面，錯了 d[v][0]=t; f1[v]=w; } elseif(t>d[v][1]) { d[v][1]=t; f2[v]=w; } } } returnd[v][0];}voidDP(intv){ inti,s,w; visit[v]=true; s=G[v].size();/* if(f1[p[v]]==v) { maxd[v]=d[v][1]; } else { maxd[v]=d[v][0]; } if(maxd[p[v]]+1>maxd[v]) { maxd[v]=maxd[p[v]]+1; }*/ for(i=0;i<s;i++) { w=G[v][i]; if(!visit[w]) { maxd[w]=0; if(f1[p[w]]==w) { maxd[w]=d[p[w]][1]+1; } else maxd[w]=d[p[w]][0]+1;/* if(maxd[w]<d[w][0])//這個if不能放在這邊算，否則會破化maxd的值，DP時就錯了，如4123時就錯了算出，maxd[3]=3。 maxd[w]=d[w][0];*///要確保maxd[v]不是從路徑v--w這邊獲得的 if(maxd[p[w]]+1>maxd[w])//開始的時候這個if沒有就錯 { maxd[w]=maxd[p[w]]+1; } DP(w); } }}voidsolve(){ dfs(1); inti; for(i=0;i<=N;i++) { visit[i]=false; } maxd[1]=0;//DP(1)前的maxd[1]的值(即根節(jié)點的maxd值)要注意一下 DP(1); intmm=INT_MAX;//DP(1)后maxd[i]的值，并不是最終節(jié)點i到所有節(jié)點的最大距離 intans[2]={-1,-1},num=0;//而是從i出發(fā)往父親節(jié)點走向所有節(jié)點的最大距離，不包括往i節(jié)點往下走的節(jié)點的距離 for(i=1;i<=N;i++) { maxd[i]=max(maxd[i],d[i][0]);//這邊算出的才是最終的的值 if(mm>maxd[i]) { mm=maxd[i]; ans[0]=i; num=0; } elseif(mm==maxd[i]) { ans[++num]=i; } } printf("%d",ans[0]); if(num==1) { printf("%d",ans[1]); } printf("\n");}intmain(){ build(); solve(); return0;}樹的最小覆蓋(pku1848最少的點通過邊覆蓋其它所有的點)解題報告：輸入有Ｎ個頂點和N-1條邊的樹。要你求最少的頂點集，使得這些頂點覆蓋所有的其他的頂點。開始的時候以為這題更那個Strategicgame是一樣題目，其實不是這樣的，那題一個頂點控制的是與頂點相鄰的邊，問你控制所有的邊最少需要幾個頂點，這題是頂點覆蓋相鄰的頂點。這個導(dǎo)致如果用樹狀DP的話，狀態(tài)和狀態(tài)轉(zhuǎn)移方程不同。但是這兩題都可以用貪心來做。//f[i][0]表示以i為根的子樹，根不取，所有點都滿足條件的最優(yōu)值//f[i][1]表示以i為根的子樹，根取，所有點都滿足條件的最優(yōu)值//f[i][2]表示以i為根的子樹，根不取，除了根之外其他點都滿足條件的最優(yōu)值(根滿足也行不滿足也行)這樣設(shè)狀態(tài)可以過，也有其他幾種不同的表示方法吧。不過好像最少都要三個狀態(tài)的對上面的三個狀態(tài)重新定義：f[i][0]表是根不取，但是根被子節(jié)點控制的最優(yōu)值f[i][1]根取的時候的最優(yōu)值f[i][2]根不取，根節(jié)點被子節(jié)點控制和或不被子節(jié)點控制狀態(tài)轉(zhuǎn)移的方程：f[i][1]=1+min{f[k][v]}k=0,1,2頂點為v為頂點i的兒子。f[i][2]=min{f[0][v],f[1][v]};表示i節(jié)點不取，但是子節(jié)點都必須滿足條件，f[i][0]=如果f[i][2]的最有值中的子節(jié)點有一個放了，那么f[i][0]=f[i][2],否則選擇一個子節(jié)點放的，其他還是取最小值（不放）最優(yōu)值#include<iostream>usingnamespacestd;constintmaxn=10000;typedefstruct{ intv; intnext;}EDGE;EDGEe[2*maxn];inth[maxn];intf[3][maxn];inten,N;boolinput(){ if(scanf("%d",&N)==EOF) { returnfalse; } inti,a,b; memset(h,-1,N*sizeof(int)); en=0; for(i=1;i<N;i++) { scanf("%d%d",&a,&b); --a; --b; e[en].v=a; e[en].next=h[b]; h[b]=en; ++en; e[en].v=b; e[en].next=h[a]; h[a]=en; ++en; } returntrue;}inlineintmin2(inta,intb){ returna<b?a:b;}inlineintmin3(inta,intb,intc){ if(a>b) a=b; if(a>c) a=c; returna;}voiddfs(intv,intp){ boolplate=false; boolleaf=true; f[0][v]=f[2][v]=0; f[1][v]=1; inti,dif=INT_MAX; for(i=h[v];i!=-1;i=e[i].next) { if(e[i].v!=p) { leaf=false; dfs(e[i].v,v); f[1][v]+=min3(f[0][e[i].v],f[1][e[i].v],f[2][e[i].v]); if(f[1][e[i].v]<=f[0][e[i].v]) { f[2][v]+=f[1][e[i].v]; plate=true; } else { f[2][v]+=f[0][e[i].v]; if(f[1][e[i].v]-f[0][e[i].v]<dif) { dif=f[1][e[i].v]-f[0][e[i].v]; } } } } if(leaf) { f[0][v]=1; f[1][v]=1; f[2][v]=0; return; } f[0][v]=f[2][v]; if(!plate) { f[0][v]+=dif; }// printf("%d%d%d%d\n",v,f[0][v],f[1][v],f[2][v]);}voidsolve(){ f[0][0]=f[1][0]=0; dfs(0,-1); intans=min2(f[0][0],f[1][0]); printf("%d\n",ans);}intmain(){ while(input()) { solve(); } return0;}蝸牛找房子（pkuTheLostHouse）題目大意：蝸牛的房子遺失在了一棵樹的某個葉子結(jié)點上，它要從根結(jié)點出發(fā)開始尋找它的房子。有一些中間結(jié)點可能會住著一些蟲子，這些蟲子會告訴蝸牛它的房子是否在以這個中間結(jié)點為根的子樹上，這樣蝸牛就不用白跑路了。當(dāng)然，如果有些結(jié)點沒有住著蟲子的話，那么可憐的蝸牛只有靠自己決定訪問順序來探索了。假設(shè)蝸牛走過一條邊的耗費都是1，且房子遺失在每個葉子結(jié)點的概率都是相等的，那么請問蝸牛找到他的房子的最小數(shù)學(xué)期望值？SampleInput5-1N1N1Y3N3N10-1N1Y1N2N2N2N3N3Y8N8N6-1N1N1Y1N3N3N0SampleOutput3.00005.00003.5000我們約定，樹上的結(jié)點數(shù)n最多為1000，每個結(jié)點的分叉數(shù)k最多為8。例如在下面的這棵樹當(dāng)中：蝸牛從根結(jié)點1出發(fā)開始尋找它的房子，它的房子可能遺失在2、4、5。在結(jié)點3上住著一只蟲子，它會告訴蝸牛，以3為根的子樹上是否有蝸牛的房子。蝸牛有兩種走法。蝸?？梢韵仍L問2，如果它在那兒不能找到房子，那么它要回到根結(jié)點1，再通過3來訪問結(jié)點4（或5），如果還是不能找到它的房子，那么它又要回到結(jié)點3，再去訪問結(jié)點5（或4）。在這種走法中，當(dāng)房子分別位于2、4、5的時候，蝸牛需要走的步數(shù)分別是1、4、6，期望值是(1+4+6)/3=11/3。顯然，這種走法沒有充分發(fā)揮蟲子在這里起到的作用。在另一種走法中，蝸牛先訪問結(jié)點3，它可以從住在3上的蟲子那里得知它的房子是否存在于4或5的信息。在這種走法中，當(dāng)房子分別位于2、4、5的時候，蝸牛需要走的步數(shù)分別是3、2、4，期望值是(3+2+4)/3=3。這種走法合理的利用了蟲子提供的信息，得到了更優(yōu)的數(shù)學(xué)期望值。算法分析：不難分析出本題的大體模型是用樹的動態(tài)規(guī)劃來求解。用Fa[i]表示蝸牛的House在i為根的子樹上的期望和，用Fb[i]表示蝸牛的House不在i為根的子樹上的時候遍歷該子樹需要的時間，用Leaves[i]表示i為根的子樹上葉子節(jié)點的數(shù)目。問題的解答就是Fa[根結(jié)點]/Leaves[根結(jié)點]。如果結(jié)點u有k個兒子,我們按照S[1]..S[k]進行訪問，F(xiàn)a[u]的計算方式是：Fa[u]=0;Fb[u]=0;fori=1tokdobeginFa[u]=Fa[u]+(Fb[u]+1)×Leaves[S[i]]+Fa[S[i]];Fb[u]=Fb[u]+Fb[S[i]]+2;end;用公式的形式可以表示為：①現(xiàn)在的問題就是如何決定訪問兒子的順序，不同的訪問順序會產(chǎn)生不同的Fa[u]。我們要使得Fa[u]盡量的小。一種直觀的方法是k！枚舉訪問順序，總體復(fù)雜度是O(nk!)，實在是很低效。用狀態(tài)壓縮的動態(tài)規(guī)劃進行二次動規(guī)的話，可以將復(fù)雜度降為O(n2kk)，勉強可以接受了。（注：由于狀態(tài)壓縮的動態(tài)規(guī)劃不是本文的重點，故這里不做展開）但是我們的研究并沒有因此停止!我們嘗試用貪心的思想來分析問題：考慮一種訪問順序中的兩個相鄰元素v和v+1，如果交換v和v+1之后得到的值不如交換前的值，那么v一定在v+1的前面了。具體證明如下：我們對公式①來進行一些處理?？梢钥闯?，交換v和v+1之后，對和是不會產(chǎn)生任何影響的，關(guān)鍵是看是增大了還是減小了。把交換前和交換后的值做差：最后得到的則只跟元素v和v+1的信息有關(guān)，于別的元素的排列情況無關(guān)，所以元素v和v+1是可比的。證畢。另外，根據(jù)這個結(jié)果，可以得出另一個結(jié)論：如果A一定放在B前，B一定放在C前，可以推導(dǎo)出A一定放在C前。證明：兩式相乘得到：證畢。上面這個結(jié)論說明，本題中的“可比性”是可以傳遞的，因此可以根據(jù)這個性質(zhì)確定出一個全序關(guān)系，因而省去了枚舉排列的部分，只需要對所有元素進行一次排序即可。時間復(fù)雜度為O(nklog2k)，非常優(yōu)秀。自己的解題報告：本題就是按照論文里的方法寫的，不過對于比較函數(shù)，開始時候按照里面的來寫錯了很錯次，試了很多比較函數(shù)都是錯的。一下這兩種比較函數(shù)都是錯的。boolcmp1(inta,intb){ return(fb[a]*1.0/leaves[a])<(fb[b]*1.0/leaves[b]);}boolcmp2(inta,intb){ return(fa[a]*1.0/leaves[a])>(fa[b]*1.0/leaves[b]);}還寫了一種比較函數(shù)在cmp1相等的情況下，在比較cmp2,也是錯的。就是看了討論里的說法：訪問每一棵子樹失敗的代價設(shè)為wi,相應(yīng)子樹的葉子數(shù)目設(shè)為li對wi/li排序之后的順序就是子樹的訪問順序在注意一下遞推式子里面的數(shù)，其實很容易想到比較函數(shù)：其實上面乘的我們也可以寫成除的，可以寫成相應(yīng)的乘的這樣保證不會有精度問題。boolcmp(inta,intb)//這個比較函數(shù)注意，開始的時候?qū)懞芏鄠€{ return(fb[a]+2)*leaves[b]<(fb[b]+2)*leaves[a];}#include<iostream>#include<algorithm>usingnamespacestd;constintmaxn=1010;intfa[maxn],fb[maxn],leaves[maxn];boolw[maxn];typedefstruct{ intv; intnext;}Edge;Edgee[maxn];inth[maxn];intn,en;boolinput(){ scanf("%d",&n); if(n==0) returnfalse; chartmp[2]; intv; en=0; memset(h,-1,sizeof(h)); scanf("%d%s",&v,tmp); if(tmp[0]=='Y') { w[1]=true; } inti; for(i=2;i<=n;++i) { scanf("%d%s",&v,tmp); e[en].v=i; e[en].next=h[v]; h[v]=en; en++; if(tmp[0]=='Y') { w[i]=true; } else { w[i]=false; } } returntrue;}boolcmp(inta,intb)//這個比較函數(shù)注意，開始的時候?qū)懞芏鄠€{ return(fb[a]+2)*leaves[b]<(fb[b]+2)*leaves[a];}voiddfs(intv){ fa[v]=fb[v]=0; inti; leaves[v]=0; if(h[v]==-1) { leaves[v]=1; return; } intseq[8],top=0;//這邊的seq必須是局部變量，因為有遞歸下去，全局的話，值會變 for(i=h[v];i!=-1;i=e[i].next) { dfs(e[i].v); seq[top++]=e[i].v; leaves[v]+=leaves[e[i].v]; } sort(seq,seq+top,cmp); for(i=0;i<top;++i) { fa[v]=fa[v]+(fb[v]+1)*leaves[seq[i]]+fa[seq[i]];//開始的時候這邊不理解，看看樣例就知道了 fb[v]=fb[v]+fb[seq[i]]+2; } if(w[v]) { fb[v]=0; }}voidsolve(){ dfs(1); printf("%.4lf\n",1.0*fa[1]/leaves[1]);}intmain(){ while(input()) { solve(); } return0;}選課(vijos1180)描述Description 學(xué)校實行學(xué)分制。每門的必修課都有固定的學(xué)分，同時還必須獲得相應(yīng)的選修課程學(xué)分。學(xué)校開設(shè)了N（N<300）門的選修課程，每個學(xué)生可選課程的數(shù)量M是給定的。學(xué)生選修了這M門課并考核通過就能獲得相應(yīng)的學(xué)分。在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如《Frontpage》必須在選修了《Windows操作基礎(chǔ)》之后才能選修。我們稱《Windows操作基礎(chǔ)》是《Frontpage》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。每門課都有一個課號，依次為1，2，3，…。例如:表中1是2的先修課，2是3、4的先修課。如果要選3，那么1和2都一定已被選修過。你的任務(wù)是為自己確定一個選課方案，使得你能得到的學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時間上的沖突。 輸入格式InputFormat 輸入文件的第一行包括兩個整數(shù)N、M（中間用一個空格隔開）其中1≤N≤300,1≤M≤N。以下N行每行代表一門課。課號依次為1，2，…，N。每行有兩個數(shù)（用一個空格隔開），第一個數(shù)為這門課先修課的課號（若不存在先修課則該項為0），第二個數(shù)為這門課的學(xué)分。學(xué)分是不超過10的正整數(shù)。 輸出格式OutputFormat 輸出文件只有一個數(shù),實際所選課程的學(xué)分總數(shù)本題是樹形DP，有一點要注意，就是本體不一定就是一個樹，可能是森林，多一個零節(jié)點，建成一課樹。開始的時候一直不知道怎么從葉子往根DP，還是從根到葉子DP，因為認(rèn)為對于內(nèi)部節(jié)點，如果其深度為h,那么它只有f[v][k](k>=h)才有狀態(tài)，才有值，所以開始的時候認(rèn)為應(yīng)該從根到葉子DP,而且還要多幾個參數(shù)，比如節(jié)點深度,子樹節(jié)點的個數(shù)等等。后來想通了，可以從葉子往根DP，也不用深度這個參數(shù)。對于每個節(jié)點，其值f[v][1~~K]（k為子樹的節(jié)點的個數(shù)）有狀態(tài)，f[1]=cost[v]其兒子只對v節(jié)點的f[v][2]才有影響，而對于v的父親節(jié)點，v只對f[w][2]有影響，而v的兒子f[v][2]的值只對f[w][3]才有影響，只樣一直傳遞上去，最后就是答案了，對于每一個節(jié)點，沒有f[v][0]這個狀態(tài)，DP的時候不用考慮0的情況。#include<iostream>#include<vector>usingnamespacestd;vector<int>G[301];intf[301][301]={0},c[301],N,M,in[301]={0};inlineintmymax(inta,intb){ returna>b?a:b;}intDP(intv){ intt,w,now,i,j,k; t=1; f[v][1]=c[v]; for(i=0;i<G[v].size();i++) { w=G[v][i]; now=DP(w); for(j=t;j>=1;j--) { for(k=1;k<=now;k++) { f[v][j+k]=mymax(f[v][j+k],f[v][j]+f[w][k]); } } t+=now; } returnt;}intmain(){ inti,j,b; scanf("%d%d",&N,&M); for(i=1;i<=N;i++) { scanf("%d%d",&b,&c[i]); if(b!=0){ G[b].push_back(i); in[i]++; } } for(j=1;j<=N;j++) if(in[j]==0) G[0].push_back(j); c[0]=0; DP(0); printf("%d\n",f[0][M+1]);//之所以要M+1是因為多了0，這個課程 return0;}樹上多少對節(jié)點距離少于給定值(pku1741)題目意思：給你一個含有N個節(jié)點的樹，問你樹中有多少個節(jié)點對其距離小于K。SampleInput5412313114235100SampleOutput8算法分析：本題是DFS+歸并排序。歸并排序真得需要好好理解一下，很多場合都用的上。歸并排序還可以用來求逆序數(shù)。對于本題：先DFS算出根結(jié)點的當(dāng)前子節(jié)點為根的子樹中所有節(jié)點在根節(jié)點的距離存于dist[to+1~st]中，然后再算當(dāng)前子節(jié)點為根的子樹中所有節(jié)點到已經(jīng)遍歷過的節(jié)點的距離小于K的對數(shù).（算的時候要利用排好序的作用），然后然歸并排序把to+1~st歸并到已經(jīng)遍歷的節(jié)點當(dāng)中。本程序很簡單，但是如果你不會，寫程序就很困難，本程序很有技巧性，如cnt的功能，如何判斷當(dāng)前子樹處理到了那個節(jié)點，返回值的設(shè)置等！#include<stdio.h>#include<string.h>#defineMN10032structEdge{ intver,next,wt;}E[MN*2];inth[MN];intdist[MN],t[MN],N,K,cnt,ans;intDFS(intv,intp){ intfrom,to,st,i,j,r,idx,w; from=to=cnt++; dist[to]=0;//初始距離為0 for(idx=h[v];idx!=-1;idx=E[idx].next) { w=E[idx].ver; if(w!=p) { st=DFS(w,v); for(i=to+1;i<=st;i++)//這個別忘，加上后才是到根節(jié)點的距離 { dist[i]+=E[idx].wt; } for(i=from,j=st;j>to;j--)//利用排序的作用 { while(i<=to&&dist[j]+dist[i]<=K) i++; ans+=i-from; } for(r=from,i=from,j=to+1;i<=to&&j<=st;) { if(dist[i]<dist[j]) t[r++]=dist[i++]; else t[r++]=dist[j++]; } while(i<=to){ t[r++]=dist[i++]; } while(j<=st) { t[r++]=dist[j++]; } for(i=from;i<=st;i++) { dist[i]=t[i]; } to=st; } } returnto;}intmain(){ inti,a,b,c,now; while(scanf("%d%d",&N,&K)!=EOF) { if(!N&&!K) break; now=1; memset(h,-1,sizeof(h)); for(i=1;i<N;i++) { scanf("%d%d%d",&a,&b,&c); E[now].wt=c; E[now].ver=a; E[now].next=h[b]; h[b]=now; now++; E[now].wt=c; E[now].ver=b; E[now].next=h[a]; h[a]=now; now++; } cnt=1; ans=0; DFS(1,-1); printf("%d\n",ans); } return0;}給樹加最少邊，使每邊都只屬于一個環(huán)(Pku1848Tree)SampleInput7121335345657SampleOutput2[動態(tài)規(guī)劃]pku18