省選講課-動(dòng)規(guī)題

動(dòng)規(guī)題選講浙江省溫州中學(xué)徐持衡動(dòng)態(tài)規(guī)劃近年來，涉及動(dòng)態(tài)規(guī)劃的各種競(jìng)賽題越來越多，幾乎每一場(chǎng)都會(huì)有一兩道題目需要用動(dòng)態(tài)規(guī)劃的方法來解決；而競(jìng)賽對(duì)選手運(yùn)用動(dòng)態(tài)規(guī)劃知識(shí)的要求也越來越高，已經(jīng)不再停留于簡單的遞推和建模上了。動(dòng)態(tài)規(guī)劃基本原理多階段決策問題如果一類活動(dòng)過程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需作出決策(采取措施)。一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過程的活動(dòng)路線，則稱它為多階段決策問題。動(dòng)態(tài)規(guī)劃基本原理各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對(duì)應(yīng)于一個(gè)策略可以確定活動(dòng)的效果，這個(gè)效果可以用一個(gè)數(shù)值來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果。動(dòng)態(tài)規(guī)劃基本原理如圖示，一個(gè)帶權(quán)有向的多段圖，要求從A到D的最短路徑的長度(下面簡稱最短距離)動(dòng)態(tài)規(guī)劃的術(shù)語階段狀態(tài)無后效性決策策略最優(yōu)性原理階段把所給求解問題的過程恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同．描述階段的變量稱為階段變量。狀態(tài)狀態(tài)表示每個(gè)階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。狀態(tài)也就是對(duì)當(dāng)前決策的限制條件。無后效性我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過程也就確定了。狀態(tài)決定了當(dāng)前決策的限制條件。決策一個(gè)階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的一種選擇（行動(dòng)）稱為決策。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個(gè)階段選擇決策時(shí)只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。策略由每個(gè)階段的決策組成的序列稱為策略。能達(dá)到最優(yōu)效果的可行策略稱為最優(yōu)策略。最優(yōu)性原理作為整個(gè)過程的最優(yōu)策略，它滿足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。最優(yōu)性原理實(shí)際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。動(dòng)規(guī)題選講最優(yōu)最大最小最長不降子序列給出一個(gè)長度為n(n<=100000)的數(shù)字序列Xi，求一個(gè)最長的子序列，使得這個(gè)子序列中的數(shù)字依次不降。X132142最長不降子序列f[i]表示第i個(gè)數(shù)字最多能作為多長的不降子序列的最后一個(gè)數(shù)字。f[i]=max{f[j]|j<i,Xi>=Xj}O(n2)X153241f122232最長不降子序列f[i]當(dāng)前可以作為第i個(gè)不降子序列的最小值?？梢宰C明f[i]在任意時(shí)刻都是不降的。用二分查找，每次找到最后一個(gè)f[i]<=Xj，用Xj更新f[i+1]O(nlogn)特殊的最長公共子序列給出兩個(gè)1到n(n<=100000)的排列，求最長公共子序列。X1123546X2423165特殊的最長公共子序列f[i,j]表示第一個(gè)序列的前i個(gè)元素和第二個(gè)序列的前j個(gè)元素的最長公共子序列。X1123546X2423165特殊的最長公共子序列f[i,j]=max{f[i–1,j],f[i,j–1],f[i–1,j–1]+ord(X1[i]=X2[i])}O(n2)X1123546X2423165特殊的最長公共子序列可以把信息轉(zhuǎn)化為求最長不降子序列。同樣可以做到O(nlogn)X1123546X2423165F423615二維最長不降子序列給出n(n<=100000)組數(shù)(Ai,Bi)，取出最多組，對(duì)于任意i<j滿足Ai<=Aj,Bi<=Bj二維最長不降子序列O(n2)的算法依然可用。要怎么改造O(nlogn)的算法？二維最長不降子序列本來的f[i]現(xiàn)在對(duì)應(yīng)一棵BST，按Ai排序，刪除Ai<=Aj且Bi<=Bj的元素j。凸多邊形三角劃分給定一個(gè)具有N（N<50）個(gè)頂點(diǎn)（從1到N編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問如何把這個(gè)凸多邊形劃分成N-2個(gè)互不相交的三角形，使得這些三角形頂點(diǎn)的權(quán)的乘積之和最??？凸多邊形三角劃分這是一道很典型的動(dòng)態(tài)規(guī)劃問題。設(shè)F[I,J]（I<J）表示從頂點(diǎn)I到頂點(diǎn)J的凸多邊形三角剖分后所得到的最大乘積，我們可以得到下面的動(dòng)態(tài)轉(zhuǎn)移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(I<K<J)目標(biāo)狀態(tài)為：F[1,N]目標(biāo)狀態(tài)為：F[i,i+n-1]分配方案數(shù)有n個(gè)不同的東西，分成m份，每份最少min個(gè)，求總方案數(shù)。(n,m<=1000)每份是相同的。分配方案數(shù)f[i,j]表示總共i個(gè)分成j份的總方案數(shù)。f[i,j]=sum{f[i-k,j-1]*C(i-1,k-1)}(k>=min)枚舉k，時(shí)間復(fù)雜度O(m*n2)分配方案數(shù)改變思路，每次處理最小的一個(gè)。分為兩種情況：在一個(gè)大小為min的組里在一個(gè)大小大于min的組里分配方案數(shù)f[i,j]=f[i-min,j-1]*C(i-1,min-1)

//第一種情況+f[i-1,j]*j//第二種情況O(n*m)交叉匹配現(xiàn)有兩行正整數(shù)，長度都小于1000。如果第一行中有一個(gè)數(shù)和第二行中的一個(gè)數(shù)相同，都為r，則我們可以將這兩個(gè)數(shù)用線段連起來。稱這條線段為r－匹配線段。例如下圖就顯示了一條3匹配線段和一條2匹配線段。交叉匹配每條a匹配線段恰好和一條b匹配線段相交，且a≠b，a,b指代任何值，并非特定值。不存在兩條線段都從一個(gè)數(shù)出發(fā)。計(jì)算出匹配線段的最多個(gè)數(shù)。交叉匹配轉(zhuǎn)移時(shí)要兩對(duì)一起轉(zhuǎn)移用f[i,j]表示第一列的前i個(gè)和第二列的前j個(gè)的最大匹配數(shù)。交叉匹配這是一個(gè)多次動(dòng)態(tài)規(guī)劃問題。設(shè)這兩行數(shù)分別保存在a[n]和b[m]中。用f(i,j)表示如下圖所示的兩行數(shù)據(jù)，可以畫出的最多的匹配線段數(shù)。交叉匹配對(duì)于這個(gè)狀態(tài)的求解，可以分如下幾種情況討論：1.沒有從a[i]出發(fā)的匹配線段。如下圖，這種情況的解即為f(i–1,j)交叉匹配2.沒有從b[j]出發(fā)的匹配線段。如下圖，這種情況的解即為f(i,j–1)交叉匹配3.a[i]和b[j]處，各引出一條匹配線段，這時(shí)必須a[i]≠b[j]。設(shè)a[i]=b[v]，b[j]=a[u]。從a[i]向b[v]，b[j]向a[u]各引一條匹配線段，這兩條線段必然相交。這種情況的解即為f(u–1,v–1)+2交叉匹配顯然，f(i,j)就是上面三種情況中的最優(yōu)值。因此，我們可以列出狀態(tài)轉(zhuǎn)移方程：其中交叉匹配如果存在a[u’]=b[j]，且u<u’<i，則用b[j]向a[u’]的匹配線段，代替b[j]向a[u]的匹配線段，所得到的解不會(huì)變差。因此，u的選擇是越靠后越好。同理，v的選擇也是越靠后越好。交叉匹配對(duì)于確定的i和j，相應(yīng)的u和v的值也是確定的，這些值可以預(yù)先求出。而求法也是利用動(dòng)態(tài)規(guī)劃。設(shè)相應(yīng)u和v的值分別為u[i,j]和v[i,j]。交叉匹配所以最后的算法復(fù)雜度為O(n*m)整個(gè)算法需要先要計(jì)算u,v數(shù)組，然后再計(jì)算f數(shù)組。交叉匹配所以最后的算法復(fù)雜度為O(n*m)整個(gè)算法需要先要計(jì)算u,v數(shù)組，然后再計(jì)算f數(shù)組。最大頒獎(jiǎng)臺(tái)在一個(gè)矩形的網(wǎng)格區(qū)域有一些壞點(diǎn)。I型頒獎(jiǎng)臺(tái)是由三個(gè)矩形相接疊成的，不能含有壞點(diǎn)，其中上方和下方的矩形的兩側(cè)必須都超出中間的矩形，否則將被誤解成T,L,J等字母。例如：最大頒獎(jiǎng)臺(tái)以下三種情況均不合法：矩陣n*m(n,m<=200)求頒獎(jiǎng)臺(tái)的最大面積最大頒獎(jiǎng)臺(tái)先用f1[i,j,k]表示第i行的第j~k列作為圖案中第1個(gè)矩形的下邊界時(shí)，所得到的最大面積。再用f2[i,j,k]表示第1個(gè)矩形下邊界為第i行的[j’,k’](j’<=j且k’>=k)的最大面積。然后用f3[i,j,k]表示第二個(gè)矩形……最大頒獎(jiǎng)臺(tái)算法效率O(n*m2)最大權(quán)值凸包給出n(n<=200)個(gè)點(diǎn)的坐標(biāo)及其權(quán)值，求凸包的點(diǎn)權(quán)值和的最大值。最大權(quán)值凸包由于要求是凸包，所以需要記錄上次的斜率。f[i,j,k]表示凸包的最左邊的點(diǎn)為i，目前的最后兩個(gè)點(diǎn)是j和k，最大的權(quán)值和。枚舉l，滿足j-k-l是凸的，然后轉(zhuǎn)移。最大權(quán)值凸包需要O(n4)改變狀態(tài)表示f[i,j,k]表示起點(diǎn)i，最后一個(gè)點(diǎn)是j，接下來一個(gè)點(diǎn)可能是k以及在j-k線以下的點(diǎn)。最大權(quán)值凸包需要預(yù)處理出斜率僅次于j-k邊的k-u[j,k]和j-v[j,k]轉(zhuǎn)移的時(shí)候f[i,j,k]就只需要更新f[i,j,v[j,k]]和f[i,k,u[j,k]]兩個(gè)值就可以了O(n3)新漢諾塔n個(gè)柱子m個(gè)盤子，求把所有的盤子從1號(hào)柱子移到n號(hào)柱子的最少步數(shù)。新漢諾塔用f[i,j]表示i個(gè)盤用j個(gè)柱子的最少移動(dòng)次數(shù)。f[i,j]=min{f[k,j]*2+f[i-k,j-1]}(i>=k>=0)滑雪路線在一張n*m的地圖中，找到一條最長的先降序后升序的路徑，要求點(diǎn)不能重復(fù)走。地圖中的高度為1到n*m整數(shù)，每個(gè)數(shù)只會(huì)出現(xiàn)一次。n,m<=50滑雪路線先按高度排序動(dòng)規(guī)，f[i,j](i<j)表示以i為起點(diǎn)，j為終點(diǎn)的一條先遞減后遞增路徑，然后枚舉k滿足k與i或j相鄰，且比i和j都要高，并更新對(duì)應(yīng)的值。土地購買FJ想要購買N個(gè)矩陣，給出每個(gè)矩陣的長A[i]和寬B[i],FJ一次可以購買一個(gè)或多個(gè)矩陣,代價(jià)是max(A[i])*max(B[i])求購買全部n個(gè)矩陣的最小代價(jià)土地購買一個(gè)顯然的結(jié)論是，對(duì)于一個(gè)矩陣，如果它被任意一個(gè)矩陣包含，那么可以不用考慮這個(gè)矩陣。按A降序排列后，可以得到O(N^2)的動(dòng)規(guī)方程F[N]=min(F[I]+A[I+1]*B[N])土地購買考慮對(duì)于剛才的轉(zhuǎn)移，就是枚舉最后一段購買的起點(diǎn)。（最后一段購買i到n）如果對(duì)于i<j,如果有F[I]+A[I+1]*B[N]<F[j]+A[j+1]*B[N]那么有(F[I]-F[J])<-B[N]*(A[I+1]-A[J+1])除了B[N]其他都是定值，而B[N]也是單調(diào)遞增的。土地購買單調(diào)隊(duì)列!O(nlogn)貨幣兌換(NOI07一試)已知未來N天內(nèi)的A券和B券的價(jià)值以及Rate。如果開始時(shí)擁有S元錢，那么N天后最多能夠獲得多少元錢。買入必須滿足買入A的數(shù)量MA和買入B的數(shù)量MB滿足：MA:MB=Rate賣出必須同時(shí)賣出p%的A券和B券n<=100000所有數(shù)均可以為實(shí)數(shù)。貨幣兌換(NOI07一試)必然存在一種最優(yōu)的買賣方案滿足：每次買進(jìn)操作使用完所有的人民幣；每次賣出操作賣出所有的金券。貨幣兌換(NOI07一試)用f[i]表示第i天的最多的錢。那么f[i]可以從前i-1天的任意一天全部買入在第i天全部賣出。也可以是從f[i-1]繼承而來。O(n2)貨幣兌換(NOI07一試)如果把每天的錢全都買入AB券那么用X[i]和Y[i]表示第i天的A券和B券數(shù)量。把一個(gè)個(gè)點(diǎn)都畫在一個(gè)平面坐標(biāo)系中。貨幣兌換(NOI07一試)如圖所示貨幣兌換(NOI07一試)最終維護(hù)一個(gè)斜率遞減的剩余點(diǎn)。二分查找最大值出現(xiàn)的斜率。壓縮狀態(tài)的動(dòng)態(tài)規(guī)劃含義：以一個(gè)集合內(nèi)的元素信息作為狀態(tài)，狀態(tài)總數(shù)為指數(shù)級(jí)別的動(dòng)態(tài)規(guī)劃。特點(diǎn)：1、本身要滿足動(dòng)態(tài)規(guī)劃的性質(zhì)：

最優(yōu)性原理、無后效性。2、數(shù)據(jù)某幾維規(guī)模比較小。集合型動(dòng)態(tài)規(guī)劃給定n個(gè)點(diǎn)的有向帶權(quán)圖，求一條經(jīng)過每個(gè)點(diǎn)一次的回路，并要求邊權(quán)和最小。范圍n<=15。集合型動(dòng)態(tài)規(guī)劃顯然對(duì)于某一個(gè)中間狀態(tài)，影響它的最后結(jié)果的僅僅是當(dāng)前所在點(diǎn)以及之前已經(jīng)經(jīng)過的點(diǎn)。而之前的路徑行走情況與之后的解無關(guān)。狀態(tài)