[計(jì)算機(jī)]dp-坐標(biāo)規(guī)則型動(dòng)態(tài)規(guī)劃-資料下載頁(yè)
2024-10-19 03:41本頁(yè)面
【正文】 ? n≤100。 向上的三角形， ? 設(shè)頂點(diǎn)坐標(biāo)為 (i,j)的三角形最大高度為 F(i,j) ? 顯然： F(i,j)=MIN{F(i1,j1),F(i1,j+1)} +1， ? 當(dāng) C[i1,j]=‘’，表示這個(gè)三角形沒(méi)被老鼠咬壞。 向下的三角形 ? 設(shè)頂點(diǎn)坐標(biāo)為 (i,j)的三角形最大高度為 G(i,j) ? 顯然： G(i,j)=MIN{G(i+1,j1),G(i+1,j+1)} +1， ? 當(dāng) C[i+1,j]=‘’，表示這個(gè)三角形沒(méi)被老鼠咬壞。 分析 ? 分別求 F(i,j)和 G(i,j) ? 1=i=n,1=j=2n1 ? 因此，時(shí)間復(fù)雜度 O(N2) ? 答案為高度的平方，證明如下： ? 假設(shè)最大高度為 W ? 則三角形個(gè)數(shù)為１ +３ +５ +…+2W1=W2 主程序 for i:=1 to n do{倒三角情況 } for j:=i to 2*ni do if (c[i,j]=39。39。)and(i mod 2=j mod 2) then{如果該位置沒(méi)被吃，而且必須是頭朝下的三角 } begin if c[i1,j]39。39。 then f[i,j]:=1 else f[i,j]:=min(f[i1,j1],f[i1,j+1])+1。{是否可以從上面的位置轉(zhuǎn)移過(guò)來(lái)堆成更大的三角形 } if f[i,j]ans then ans:=f[i,j]。 end。 {正三角情況程序與上類似 } 總結(jié) ? 規(guī)則類動(dòng)態(tài)規(guī)劃有一個(gè)共性，那就是在一個(gè)矩陣中（一般是二維矩陣，當(dāng)然可能有更加復(fù)雜的圖形）給出一些規(guī)則，然后按規(guī)則去做某些決策，我們思考這類問(wèn)題的基本方法是：以坐標(biāo)為狀態(tài)，坐標(biāo)之間的轉(zhuǎn)換關(guān)系，一般利用問(wèn)題給出的規(guī)則進(jìn)行決策轉(zhuǎn)移。如下圖。 ? 狀態(tài)轉(zhuǎn)移方程一般可描述如下： F(i,j)=Max{f(i1,k)}+決策；這里 k為規(guī)則數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1