樹形動態(tài)規(guī)劃(信息學競賽)_第1頁
樹形動態(tài)規(guī)劃(信息學競賽)_第2頁
樹形動態(tài)規(guī)劃(信息學競賽)_第3頁
樹形動態(tài)規(guī)劃(信息學競賽)_第4頁
樹形動態(tài)規(guī)劃(信息學競賽)_第5頁
已閱讀5頁,還剩15頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

樹狀動規(guī)1333:VIJOS-P1180選課想要選修某個課程,那么它的先修課必須要被選擇。多叉樹轉(zhuǎn)二叉樹動歸。首先大家先了解多叉樹轉(zhuǎn)二叉樹。原則:二叉樹的結(jié)點x的左兒子為x的兒子,右兒子是x的兄弟。即左兒子,右兄弟原則。1333:選課(多叉樹轉(zhuǎn)二叉樹)具體實現(xiàn)方法:使用數(shù)組模擬二叉樹L[x]:表示X的左兒子是誰!初值-1R[x]:表示X的右兒子是誰!也就是X的兄弟,初值-1last[x]:表示原樹中x的當前一個子節(jié)點son1現(xiàn)在的位置,假如x的另外一個兒子son2,要插入到二叉樹中那么根據(jù)左兒子右兄弟的原則,既然son2跟son1為兄弟,那么就放到son1所在位置的右子樹即可!代碼:voidbuild(intx,inty)//y的父親結(jié)點為x{if(L[x]==-1) L[x]

=

y;else R[

last[x]

]

=

y;last[x]=y;}1333:VIJOS-P1180選課狀態(tài)F(x,y):表示節(jié)點x取y門課得最高學分方程F(x,y)=max{F(R[x],k),F(L[x],k-1)+a[x]+F(R[x],y-k)}k=0,1,..yF(L[x],k-1)+a[x]:表示左孩子選了k-1門課及包括課程x,共k門課的最大學分。F(R[x],y-k)

表示右孩子只能選y-k門課的最大得分。分析出來了這么多,代碼如何寫才是關(guān)鍵,否則都是空中樓閣。我們引入記憶化搜索的思想,即每深搜一步,把搜做到的結(jié)果保存起來,當下次搜索到同樣的位置時,直接使用!記憶化搜索經(jīng)典題目:1911滑雪&&1257Functionintwork(intpos,intk){if(pos<0||k<=0)return0;

//遞歸退出條件if(f[pos][k]!=-1)returnf[pos][k];

//如果這個值以前被計算過,直接返回這個值f[pos][k]=work(r[pos],k);

//左子樹不選任何一個for(inti=0;i<=k-1;i++)f[pos][k]=max(f[pos][k],

work(l[pos],i)+work(r[pos],k-i-1)+s[pos]);

//動規(guī)過程returnf[pos][k];}2140:通向自由的鑰匙通向自由的鑰匙被放n個房間里,這n個房間由n-1條走廊連接。注意:這就是一棵樹。本題的動規(guī)的過程與上一題選課是一樣的唯一不同的是題目給出樹的根為1,還有樹的聯(lián)通性。建二叉樹樹的過程是需要大家仔細思考的。2140:通向自由的鑰匙voidbuild(intx){for(inti=1;i<=n;i++)if(d[x][i]){d[x][i]=d[i][x]=0;if(

ls[x]==-1)

ls[x]=i;elsers[

last[x]

]=i;last[x]=i;build(i);}}1273:加分二叉樹每一個結(jié)點有一個權(quán)值,給定的序列是中序遍歷的點權(quán)序列。狀態(tài)f[i][j]表示從i到j(luò)的中序序列組成的二叉樹最大加分值。方程f[i][j]=max{f[i][k-1]*f[k+1][j]+f[k][k]}i<=k<=jf[i][k-1]和f[k+1][j]直接拿過來用肯能不會求出最大的f[i][j],所以要引入記憶化的思想,遞歸的求出這兩個的值。1273:加分二叉樹longlongwork(intx,inty){

if(x>y)returnf[x][y]=1;if(f[x][y]!=-1)returnf[x][y];for(intk=0;k<=y-x;k++)if(f[x][y]<f[x+k][x+k]+work(x,x+k-1)*work(x+k+1,y)){f[x][y]=f[x+k][x+k]+work(x,x+k-1)*work(x+k+1,y);root[x][y]=x+k; //記錄x到y(tǒng)區(qū)間的根,以便最后遞歸輸出先根遍歷。}returnf[x][y];}POJ2342Anniversaryparty題意:一個人不同他的直屬上司一起參加舞會,問參會人員的權(quán)值和的最大值。顯然每個人只有兩種狀態(tài)參加或者不參加狀態(tài)f[i][0]表示第i個人不參加,f[i][1]表示此人參加,所的得到的子樹的最大值。f[i][1]+=f[j][0]; j是其下屬的標號f[i][0]+=max{f[j][1],f[j][0]}本題使用鏈式前向星存邊,找出根rootans=max{f[root][0],f[root][1]};POJ2342Anniversarypartyvoidwork(intx){

f[x][0]=0

,

f[x][1]=a[x];

//初始化 for(inty,i=head[x];i;i=next[i]) { y=to[i]; //y為x的子節(jié)點 work(y); //先處理完y才能動規(guī)x f[x][0]+=max(f[y][0],f[y][1]); f[x][1]+=f[y][0]; }}POJ3342PartyatHali-Bula基本題意與2342相同,需要特別判斷與會名單是否唯一!思考判定方法?是否有特例!動規(guī)伴隨著深搜,只需要考慮深搜時候的局部情況即可判定全局情況。即if(f[x][0]==f[x][1]&&f[y][1]==f[y][0])flag=0;思考當n==2時,只能一個人與會,名單不確定。但是使用上面的判斷就不行了,需要特判一下即可。POJ2486AppleTreeN叉蘋果樹,結(jié)點上有蘋果,問一共走k步,所能吃到的蘋果的最大值。其中從A->B算一步,返回B->A再算一步。狀態(tài)f[0][i][j]表示從i點走j步再回到i的最大值狀態(tài)f[1][i][j]表示從i點走j步不回到i的最大值f[0][x][j+2]=max{f[0][x][j+2],f[0][y][k]+f[0][x][j-k]}f[1][x][j+2]=max{f[1][x][j+2],f[0][y][k]+f[1][x][j-k]}f[1][x][j+1]=max{f[1][x][j+1],f[1][y][k]+f[0][x][j-k]}POJ2486AppleTreevoiddfs(intx){

v[x]=1;

for(inti=0;i<=step;i++)f[1][x][i]=f[0][x][i]=a[x];

ints=t[x].size();

for(inty,i=0;i<s;i++)

{

y=t[x][i];

if(!v[y])

{ dfs(y); for(intj=step;j>=0;j--)

for(intk=0;k<=j;k++)

{

f[0][x][j+2]=max(f[0][x][j+2],f[0][y][k]+f[0][x][j-k]);

f[1][x][j+2]=max(f[1][x][j+2],f[0][y][k]+f[1][x][j-k]);

f[1][x][j+1]=max(f[1][x][j+1],f[1][y][k]+f[0][x][j-k]);

}

}

}}POJ3659CellPhoneNetwork題意:給出一棵樹,樹的每個節(jié)點都可以放信號塔,放信號塔的節(jié)點可以覆蓋到它周圍的節(jié)點,問選擇最少的建信號塔的方案,使得樹的所有節(jié)點都被覆蓋。這樣的問題叫做:最小支配集問題,使用樹形動歸來處理??紤]每個結(jié)點只有兩種狀態(tài),放或者不放信號塔。其中如果這個點不放信號塔,并且還需要被覆蓋,又有兩種情況:一是其父親結(jié)點放信號塔,二是其子節(jié)點中有一個放了信號塔??偨Y(jié)起來每個結(jié)點有三種情況:f[x][0]:x點的父親結(jié)點放塔,以x為根的子樹最少信號塔數(shù)f[x][1]:x點的子節(jié)點放塔,以x為根的子樹的最少信號塔數(shù)f[x][2]:x點本身放信號塔,以x為根的子樹最少信號塔數(shù)POJ3659CellPhoneNetwork那么動態(tài)方程為:設(shè)y為x的子結(jié)點f[x][0]+=min{f[y][1],f[y][2]}f[x][2]+=min{f[y][0],f[y][2]}f[x][1]的情況比較復(fù)雜,需要單獨討論了。x的子節(jié)點y中是否存在y的自己覆蓋小于y的子節(jié)點z的覆蓋,如果存在(f[y][2]<f[y][1]),那么這個y的分支就一定會被選中,進而輻射到y(tǒng)的根節(jié)點x。此時f[x][1]=f[x][0];如果上述情況沒有出現(xiàn)的話,只能選擇一個最優(yōu)的y,使得y點放信號塔,來輻射到x。令temp=f[y][2]-f[y][1];那么f[x][1]=f[x][0]+temp;至此,動態(tài)轉(zhuǎn)移方程就已經(jīng)寫完了,雖然有些復(fù)雜,但是對于我們深入理解動態(tài)規(guī)劃有很深的影響。POJ3659CellPhoneNetwork結(jié)點的初值:f[x][0]=0;f[x][1]=0;f[x][2]=1;如果是葉子結(jié)點呢?if(葉子)f[x][1]=1<<30;最后的ans呢?ans=min(f[root][1],f[root][2])poj3398PerfectService同樣是最小支配集問題。我們使用另類的貪心方法來解決。1、深搜遍歷,把深搜的順序記錄下來。其實深搜的順序就是先根遍歷的順。2、根據(jù)先跟遍歷的順序逆向處理,也就是相當于回溯的過程。3、如果一個結(jié)點x的覆蓋狀態(tài)mark[x]==0,并且如果其根fa[x]的是否為server的狀態(tài)為0,即set[fa[x]]==0,那么ans++,set[fa[x]]=1;4、不管set[fa[x]]是否為0,都要標記x,fa[x],fa[fa[x]]的狀態(tài)為覆蓋。思考為什么?poj3398PerfectServicevoiddfs(intx){ deep[++num]=x; for(inty,i=head[x];i;i=next[i]){ y=to[i]; if(!v[y]){ v[y]=1

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論