NOIP的DP總結(jié)之DP類型

長(zhǎng)郡范進(jìn)Dp類型總結(jié)Content資源型dp01背包完全背包多重背包二維費(fèi)用背包分組背包有依賴的背包泛化物品背包問題的經(jīng)典變形背包問題的搜索解法背包附題機(jī)器分配線性dp區(qū)間dp（剖分問題）平面dp（地圖dp、坐標(biāo)dp）樹型dp字符串dp貪心dp多進(jìn)程dp狀壓dp判定型dp目標(biāo)型dp概率dp二次dp（雙重動(dòng)態(tài)規(guī)劃）遞推問題排列dp計(jì)數(shù)問題關(guān)于記憶化搜索加優(yōu)化dp此部分總結(jié)的是dp類型。雖然總結(jié)的是dp，但我把遞推也放了進(jìn)來(lái)。嚴(yán)格來(lái)說(shuō)，遞推不屬于dp問題，因?yàn)閐p不僅有遞推過程，還有決策（即取最優(yōu)），但廣義的dp是可以包含遞推的，遞推是一類簡(jiǎn)單的、特殊的dp，畢竟dp與遞推密不可分。Dp類型主要分為純粹dp問題和復(fù)合dp問題。一資源型主要是背包，背包部分的資料來(lái)源主要是《背包九講》，另外也有自己的一些補(bǔ)充。背包部分可以添加個(gè)叫“+-1背包”的家伙（屬判定型dp）；其次還有機(jī)器分配類問題。01背包這個(gè)是最基礎(chǔ)的。首先要注意問法，是否必須完全裝滿，若是，則初值除f[i,0]=0外全賦值為負(fù)無(wú)窮?？臻g優(yōu)化：二維變一維，注意枚舉順序要變?yōu)閐ownto！時(shí)間優(yōu)化：內(nèi)層枚舉的下界取max{V-sum{w[i..n]},c[i]}相關(guān)題目：01背包母題，采藥，poj2184，poj1882，poj1252，poj2063，poj1717，poj1203變形：1判定性01背包：裝箱問題，石子歸并（裝half箱），補(bǔ)圣衣，擠牛奶，積木城堡2多包限制順序型01背包：USACORaucousRockers（多個(gè)背包，不可以重復(fù)放物品，但放物品的順序有限制。）F[I,j,k]表示決策到第i個(gè)物品、第j個(gè)背包，此背包花費(fèi)了k的空間。f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t]+p)完全背包空間優(yōu)化：變?yōu)橐痪S。注意順序枚舉。（對(duì)應(yīng)于時(shí)間優(yōu)化4）時(shí)間優(yōu)化（前3個(gè)其實(shí)都用不上，只是了解下思想）：1若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。首先將費(fèi)用大于V的物品去掉，然后使用類似計(jì)數(shù)排序的做法，計(jì)算出費(fèi)用相同的物品中價(jià)值最高的是哪個(gè)，可以O(shè)(V+N)地完成這個(gè)優(yōu)化。這個(gè)優(yōu)化一般作用較小，非常必要時(shí)再用。2轉(zhuǎn)化的思想（此處未優(yōu)化）：將物品i拆成V/c[i]個(gè)。3更高效的轉(zhuǎn)化方法是：把第i種物品拆成費(fèi)用為c[i]*2^k、價(jià)值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<=V。這是二進(jìn)制的思想，因?yàn)椴还茏顑?yōu)策略選幾件第i種物品，總可以表示成若干個(gè)2^k件物品的和。這樣把每種物品拆成O(logV/c[i])件物品，是一個(gè)很大的改進(jìn)。4O(nv)的方法：將01背包的費(fèi)用枚舉由倒序改為順序即可。（值得一提的是，上面的偽代碼中兩層for循環(huán)的次序可以顛倒。這個(gè)結(jié)論有可能會(huì)帶來(lái)算法時(shí)間常數(shù)上的優(yōu)化。）題目：完全背包母題，hdu1114，soj3664，系統(tǒng)可靠性多重背包原始方程：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}復(fù)雜度是O(V*Σn[i])。優(yōu)化：1物品i拆分成num[i]個(gè)（復(fù)雜度不變）。2二進(jìn)制拆分，將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來(lái)的費(fèi)用和價(jià)值乘以這個(gè)系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。例如，如果n[i]為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。轉(zhuǎn)化為了復(fù)雜度為O(V*Σlogn[i])的01背包問題。可以證明正確性。證明：若x=2^k-1，用1，2，4……2^(k-1)進(jìn)行01選取可以組合1到x之間的任意一個(gè)數(shù)；若x=2^k-1+y,(1<=y<2^k),用1，2，3……2^(k-1),y進(jìn)行01選取可以組合1到x之間的任意一個(gè)數(shù)，為什么呢？對(duì)于2^k<=w<=x,有w=u+y,其中必有1<=u<=2^k-1,因此u可以通過01選取組合，從而w可以通過01選取組合。代碼：procedureMultiplePack(cost,weight,amount)ifcost*amount>=VCompletePack(cost,weight)returnintegerk=1whilek<amountZeroOnePack(k*cost,k*weight)amount=amount-kk=k*2ZeroOnePack(amount*cost,amount*weight)3單調(diào)隊(duì)列優(yōu)化[O(nc)]對(duì)于第i種物品來(lái)說(shuō)，已知體積v，價(jià)值w，數(shù)量k，那么可以按照當(dāng)前枚舉的體積j對(duì)v的余數(shù)把整個(gè)動(dòng)規(guī)數(shù)組分成v份，以下是v=3的情況：我們可以把每一份分開處理，假設(shè)余數(shù)為d?，F(xiàn)在看到分組以后，編號(hào)j可以從j-k到j(luò)-1中的任意一個(gè)編號(hào)轉(zhuǎn)移而來(lái)（因?yàn)橄噜彽捏w積正好相差v），這看上去已經(jīng)和區(qū)間最大值有點(diǎn)相似了。但是注意到由于體積不一樣，顯然體積大的價(jià)值也會(huì)大于等于體積小的，直接比較是沒有意義的，所以還需要把價(jià)值修正到同一體積的基礎(chǔ)上。比如都退化到d，也就是說(shuō)用F[j*v+d]-j*w來(lái)代替原來(lái)的價(jià)值進(jìn)入隊(duì)列。代碼：procedureinsert(x,y:longint);//插入到一個(gè)價(jià)值單調(diào)遞減，使用次數(shù)單調(diào)遞增的隊(duì)列中

begin

while(l<=r)and(b[r]<=y)dodec(r);

inc(r);a[r]:=x;b[r]:=y;

end;begin

readln(n,m);

//n為物品個(gè)數(shù)、m為背包容量

fori:=1tondo

begin

read(v,w,c);

//讀入當(dāng)前物品：v為物品體積、w為物品價(jià)值、c為物品可用次數(shù)

ifmdivv<cthenc:=mdivv;

//最多可使用次數(shù)

fork:=0tov-1do

//把所有的體積按除以v的余數(shù)劃分為0~v-1

begin

l:=1;r:=0;

//清空隊(duì)列

forj:=0to(m-k)divvdo

//余數(shù)為k的又分為k,v+k,2*v+k…j*v+k…

begin

insert(j,f[j*v+k]-j*w);

//等效于把體積統(tǒng)一到k，價(jià)值減去j*w，這樣比較優(yōu)劣才有意義

whilea[l]<j-cdoinc(l);

//刪除次數(shù)超過c的

f[j*v+k]:=b[l]+j*w;

//用隊(duì)列頭的值更新f[j*v+k]

end;

end;

end;

writeln(f[m]);end.題目：砝碼秤重，tyvj1086，zoj2156，poj2392，hdu1085Poj1014，divide（見dp2）二維費(fèi)用背包就是限制條件多了一個(gè)，變成了二維容量，從而狀態(tài)多了一維而已。題目：hdu3236，打包（見dpset）poj2184分組背包有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。這個(gè)問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說(shuō)設(shè)f[k][v]表示前k組物品花費(fèi)費(fèi)用v能取得的最大權(quán)值，則有:f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬于組k}使用一維數(shù)組的偽代碼如下：for所有的組kforv=V..0for所有的i屬于組kf[v]=max{f[v],f[v-c[i]]+w[i]}注意這里的三層循環(huán)的順序,“forv=V..0”這一層循環(huán)必須在“for所有的i屬于組k”之外。這樣才能保證每一組內(nèi)的物品最多只有一個(gè)會(huì)被添加到背包中。小優(yōu)化：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。首先將費(fèi)用大于V的物品去掉，然后使用類似計(jì)數(shù)排序的做法，計(jì)算出費(fèi)用相同的物品中價(jià)值最高的是哪個(gè)，可以O(shè)(V+N)地完成這個(gè)優(yōu)化。題目：hdu3033，hdu3449有依賴的背包簡(jiǎn)化的問題這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說(shuō)，i依賴于j，表示若選物品i，則必須選物品j。為了簡(jiǎn)化起見，我們先設(shè)沒有某個(gè)物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時(shí)依賴多件物品這個(gè)問題由NOIP2006金明的預(yù)算方案一題擴(kuò)展而來(lái)。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個(gè)問題的簡(jiǎn)化條件可知所有的物品由若干主件和依賴于每個(gè)主件的一個(gè)附件集合組成。按照背包問題的一般思路，僅考慮一個(gè)主件和它的附件集合?？墒?，可用的策略非常多，包括：一個(gè)也不選，僅選擇主件，選擇主件后再選擇一個(gè)附件，選擇主件后再選擇兩個(gè)附件……無(wú)法用狀態(tài)轉(zhuǎn)移方程來(lái)表示如此多的策略。（事實(shí)上，設(shè)有n個(gè)附件，則策略有2^n+1個(gè)，為指數(shù)級(jí)。）轉(zhuǎn)化：考慮到所有這些策略都是互斥的（也就是說(shuō)，你只能選擇一種策略），所以一個(gè)主件和它的附件集合實(shí)際上對(duì)應(yīng)于分組背包中的一個(gè)物品組，每個(gè)選擇了主件又選擇了若干個(gè)附件的策略對(duì)應(yīng)于這個(gè)物品組中的一個(gè)物品，其費(fèi)用和價(jià)值都是這個(gè)策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個(gè)好的算法，因?yàn)槲锲方M中的物品還是像原問題的策略一樣多。優(yōu)化對(duì)于一個(gè)物品組中的物品，所有費(fèi)用相同的物品只留一個(gè)價(jià)值最大的，不影響結(jié)果。所以，我們可以對(duì)主件i的“附件集合”先進(jìn)行一次01背包，得到費(fèi)用依次為0..V-c[i]所有這些值時(shí)相應(yīng)的最大價(jià)值f'[0..V-c[i]]。那么這個(gè)主件及它的附件集合相當(dāng)于V-c[i]+1個(gè)物品的物品組，其中費(fèi)用為c[i]+k的物品的價(jià)值為f'[k]+w[i]。也就是說(shuō)原來(lái)指數(shù)級(jí)的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉(zhuǎn)化為V-c[i]+1個(gè)物品的物品組，就可以直接應(yīng)用分組背包的算法解決問題了。更一般的問題：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說(shuō)，主件的附件仍然可以具有自己的附件集合，限制只是每個(gè)物品最多只依賴于一個(gè)物品（只有一個(gè)主件）且不出現(xiàn)循環(huán)依賴。解決這個(gè)問題仍然可以用將每個(gè)主件及其附件集合轉(zhuǎn)化為物品組的方式。事實(shí)上，這是一種樹形DP，其特點(diǎn)是每個(gè)父節(jié)點(diǎn)都需要對(duì)它的各個(gè)兒子的屬性進(jìn)行一次DP以求得自己的相關(guān)屬性。這已經(jīng)觸及到了“泛化物品”的思想。這個(gè)“依賴關(guān)系樹”每一個(gè)子樹都等價(jià)于一件泛化物品，求某節(jié)點(diǎn)為根的子樹對(duì)應(yīng)的泛化物品相當(dāng)于求其所有兒子的對(duì)應(yīng)的泛化物品之和。樹形轉(zhuǎn)鏈?zhǔn)筋}目：選課：有n^2做法。金明的預(yù)算方案泛化物品定義：考慮這樣一種物品，它并沒有固定的費(fèi)用和價(jià)值，而是它的價(jià)值隨著你分配給它的費(fèi)用而變化。（詳見背包九講）背包問題的經(jīng)典變形1輸出方案2輸出字典序最小的最優(yōu)方案先逆序化，再普通dp。只是在輸出方案時(shí)要注意，如果f[i][v]==f[i-1][i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同時(shí)成立，應(yīng)該按照后者（即選擇了物品i）來(lái)輸出方案。3求方案總數(shù)即裝滿背包或?qū)⒈嘲b至某一指定容量的方案總數(shù)。對(duì)于這類改變問法的問題，一般只需將狀態(tài)轉(zhuǎn)移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，轉(zhuǎn)移方程即為f[i][v]=sum{f[i-1][v],f[i][v-c[i]]}初始條件f[0][0]=1。4求最優(yōu)方案總數(shù)這個(gè)較簡(jiǎn)單。5求次優(yōu)解、第K優(yōu)解維護(hù)一個(gè)k優(yōu)解的有序序列，合并采用歸并法可達(dá)到O(k)，故總復(fù)雜度為最優(yōu)解問題的k倍。背包問題的搜索方法背包問題并不是所有的都可以dp，有些需要搜索！1剪枝方法：最優(yōu)性與可行性2搜索順序的選擇：性價(jià)比法，體積大的放前面，隨機(jī)化數(shù)據(jù)（以防出題人坑爹）3子集和問題（以前l(fā)yp似乎出過）：二分+hash。4dp？搜索？在看到一道背包問題時(shí)，應(yīng)該用搜索還是動(dòng)態(tài)規(guī)劃呢？首先，可以從數(shù)據(jù)范圍中得到命題人意圖的線索。如果一個(gè)背包問題可以用DP解，V一定不能很大，否則O(VN)的算法無(wú)法承受，而一般的搜索解法都是僅與N有關(guān)，與V無(wú)關(guān)的。所以，V很大時(shí)（例如上百萬(wàn)），命題人的意圖就應(yīng)該是考察搜索。另一方面，N較大時(shí)（例如上百），命題人的意圖就很有可能是考察動(dòng)態(tài)規(guī)劃了。另外，當(dāng)想不出合適的動(dòng)態(tài)規(guī)劃算法時(shí)，就只能用搜索了。例如看到一個(gè)從未見過的背包中物品的限制條件，無(wú)法想出DP的方程，只好寫搜索以謀求一定的分?jǐn)?shù)了。崔天翼大牛推薦的相關(guān)題目（USACO）Inflate(+)（基本01背包）Stamps(+)(!)（對(duì)初學(xué)者有一定挑戰(zhàn)性）MoneyNuggetsSubsetsRockers(+)（另一類有趣的“二維”背包問題）Milk4(!)（很怪的背包問題問法，較難用純DP求解）機(jī)器分配簡(jiǎn)單的二維dp+-1背包二線性dp何謂線性dp？有人認(rèn)為是按時(shí)間復(fù)雜度來(lái)定義：復(fù)雜度由n惟一確定，且不能繼續(xù)優(yōu)化的dp為線性dp。我這里不做嚴(yán)格定義（也沒找到理論的嚴(yán)格定義）。暫且理解為其dp的結(jié)構(gòu)為線型的、鏈?zhǔn)降模瑓^(qū)別于地圖型（坐標(biāo)型），樹型，圖型等。也可理解為可以從頭到尾（或從尾到頭）按數(shù)據(jù)列的生成順序dp的一類dp問題。因此狹義地講，區(qū)間dp也不屬于線形的。疊放箱子（？見dp2）買車票文字游戲最佳加法表達(dá)式最大乘積f[i,j]=max(f[i-1,j-1]*w[j,i])

(0<=k<=n)(1<j<=i<=n)巴比倫塔硬幣問題最長(zhǎng)前綴砝碼秤重書的復(fù)制硬幣組成問題花店櫥窗布置問題(IOI99試題)Tom的煩惱可用數(shù)據(jù)結(jié)構(gòu)優(yōu)化區(qū)間最值。數(shù)字游戲統(tǒng)計(jì)單詞個(gè)數(shù)（noip）1的最小操作序列積木游戲（NOI’97）f[I,j,k]表示第i個(gè)積木（k面朝上）放在第j根柱子上的最大高度和則：f[I,j,k]=max{f[x,j,z],f[x,j-1,z]}+h[I,k].復(fù)雜度O（n^2m）.化工廠裝箱員CEOI2005service打鼴鼠描述Description根據(jù)這個(gè)特點(diǎn)阿Q編寫了一個(gè)打鼴鼠的游戲：在一個(gè)n*n的網(wǎng)格中，在某些時(shí)刻鼴鼠會(huì)在某一個(gè)網(wǎng)格探出頭來(lái)透透氣。你可以控制一個(gè)機(jī)器人來(lái)打鼴鼠，如果i時(shí)刻鼴鼠在某個(gè)網(wǎng)格中出現(xiàn)，而機(jī)器人也處于同一網(wǎng)格的話，那么這個(gè)鼴鼠就會(huì)被機(jī)器人打死。而機(jī)器人每一時(shí)刻只能夠移動(dòng)一格或停留在原地不動(dòng)。機(jī)器人的移動(dòng)是指從當(dāng)前所處的網(wǎng)格移向相鄰的網(wǎng)格，即從坐標(biāo)為（i,j）的網(wǎng)格移向(i-1,j),(i+1,j),(i,j-1),(i,j+1)四個(gè)網(wǎng)格，機(jī)器人不能走出整個(gè)n*n的網(wǎng)格。游戲開始時(shí)，你可以自由選定機(jī)器人的初始位置。

現(xiàn)在你知道在一段時(shí)間內(nèi)，鼴鼠出現(xiàn)的時(shí)間和地點(diǎn)，希望你編寫一個(gè)程序使機(jī)器人在這一段時(shí)間內(nèi)打死盡可能多的鼴鼠。輸入格式InputFormat文件第一行為n（n<=1000）,m（m<=10000），其中m表示在這一段時(shí)間內(nèi)出現(xiàn)的鼴鼠的個(gè)數(shù)，接下來(lái)的m行每行有三個(gè)數(shù)據(jù)time,x,y表示有一只鼴鼠在游戲開始后time個(gè)時(shí)刻，在第x行第y個(gè)網(wǎng)格里出現(xiàn)了一只鼴鼠。Time按遞增的順序給出。注意同一時(shí)刻可能出現(xiàn)多只鼴鼠，但同一時(shí)刻同一地點(diǎn)只可能出現(xiàn)一只鼴鼠。輸出格式OutputFormat輸出文件中僅包含一個(gè)正整數(shù)，表示被打死鼴鼠的最大數(shù)目。樣例輸入SampleInput22111222樣例輸出SampleOutput1隱形的翅膀背景Background小杉終于進(jìn)入了天堂。他看到每個(gè)人都帶著一雙隱形翅膀，他也想要。

（小杉是怎么看到的？……）描述Description天使告訴小杉，每只翅膀都有長(zhǎng)度，兩只翅膀的長(zhǎng)度之比越接近黃金分割比例，就越完美。

現(xiàn)在天使給了小杉N只翅膀，小杉想挑出一對(duì)最完美的。輸入格式InputFormat每組測(cè)試數(shù)據(jù)的

第一行有一個(gè)數(shù)N(2<=N<=30000)

第二行有N個(gè)不超過1e5的正整數(shù)，表示N只翅膀的長(zhǎng)度。

20%的數(shù)據(jù)N<=100輸出格式OutputFormat對(duì)每組測(cè)試數(shù)據(jù)輸出兩個(gè)整數(shù)，分兩行，表示小杉挑選出來(lái)的一對(duì)翅膀。

注意，比較短的在前，如果有多對(duì)翅膀的完美程度一樣，請(qǐng)輸出最小的一對(duì)。樣例輸入SampleInput42346樣例輸出SampleOutput23Vijos1198最佳課題選擇ifj-k>=0thenf[I,j]:=Min(f[i,j],f[i-1,j-k]+time(i,k));IOI2000郵局問題[問題描述]按照遞增順序給出一條直線上坐標(biāo)互不相同的n個(gè)村莊，要求從中選擇p個(gè)村莊建立郵局，每個(gè)村莊使用離它最近的那個(gè)郵局，使得所有村莊到各自所使用的郵局的距離總和最小。試編程計(jì)算最小距離和，以及郵局建立方案。思路一：現(xiàn)以f[i,j]表示安排前i個(gè)村莊使用前j個(gè)郵局，通過某種安排手段，使這i個(gè)村莊分別到這j個(gè)郵局中最近的一個(gè)的距離之和的所取到的最小值。F[i,j]=min{f[k,j-1]+c[k+1,i]}(1<=k<i)C[A,B]表示分配A至B這（B-A+1）個(gè)村莊使用一個(gè)新的郵局，通過某種安排新郵局的手段，使A至B這（B-A+1）個(gè)村莊分別到這個(gè)新郵局的距離之和所取到的最小值。那么，怎么求c數(shù)組呢?此問題相當(dāng)于郵局?jǐn)?shù)為1的原問題的一種特殊情況。即，給定N個(gè)村莊的X坐標(biāo)，要求安排一個(gè)郵局，使各村莊到該郵局的距離和為最小，求郵局坐標(biāo)。引論（盡管題目條件已給出了這個(gè)限制，證一下也無(wú)妨）：最優(yōu)解必定可使得郵局坐落在一個(gè)村莊上。假設(shè)將郵局建在A和B村莊之間，與A相距a，與B相距b，A左邊共有x個(gè)村莊（含A）使用該郵局，它們到A的距離和為SA；B右邊共有y個(gè)村莊（含B）使用該郵局，它們到B的距離和為SB。則cost=SA+SB+ax+by.但若建在A處，則costA=SA+SB+(a+b)y;但若建在B處，則costB=SA+SB+(a+b)x.當(dāng)x=y時(shí)，三中方案皆可以；當(dāng)x>y時(shí)，建在A處更優(yōu)；當(dāng)x<y時(shí)，建在B處更優(yōu)。由此可見，最優(yōu)解必定可使得郵局坐落在一個(gè)村莊上。結(jié)論：對(duì)于n個(gè)村莊，郵局建在第(ndiv2+1)個(gè)村莊最優(yōu)。證明：有引論知，對(duì)于n=x+y,若x>y,則郵局選址會(huì)不斷往左靠，直到x=y。x<y時(shí)也如此。即總有往中間靠的趨勢(shì)！思路二：f[i,j]表示第j個(gè)郵局建在第i個(gè)村莊的最小值。F[I,j]:=min{f[k,j-1]+c[k,i]}.(1<=k<i)C[a,b]表示在相鄰郵局建在a和b村莊時(shí)，a到b間的各村莊到所對(duì)應(yīng)郵局的最小距離和。思路三：四邊形不等式優(yōu)化。（網(wǎng)上有人這樣講，但目前我沒了解）三區(qū)間dp（剖分問題）石子合并變式：能量項(xiàng)鏈，多邊形剖分，最少矩陣乘法次數(shù)取數(shù)游戲加分二叉樹決斗在路易十三和紅衣主教黎塞留當(dāng)權(quán)的時(shí)代，發(fā)生了一場(chǎng)決斗。N（2<=n<=500）個(gè)人站成一個(gè)圈，依次抽簽。抽中的人和他右邊的人決斗，負(fù)者出圈。這場(chǎng)決斗的最終結(jié)果關(guān)鍵取決于決斗的順序?，F(xiàn)書籍任意兩決斗中誰(shuí)能勝出的信息，但“A贏了B”這種關(guān)系沒有傳遞性。例如，A比B強(qiáng)，B比C強(qiáng)，C比A強(qiáng)。如果A和B先決斗，C最終會(huì)贏，但如果B和C決斗在先，則最后A會(huì)贏。顯然，他們?nèi)酥械牡谝粓?chǎng)決斗直接影響最終結(jié)果。假設(shè)現(xiàn)在n個(gè)人圍成一個(gè)圈，按順序編上編號(hào)1~n。一共進(jìn)行n-1場(chǎng)決斗。第一場(chǎng)，其中一人（設(shè)i號(hào)）和他右邊的人（即i+1號(hào)，若i=n，其右邊人則為1號(hào)）。負(fù)者被淘汰出圈外，由他旁邊的人補(bǔ)上他的位置。已知n個(gè)人之間的強(qiáng)弱關(guān)系（即任意兩個(gè)人之間輸贏關(guān)系）。如果存在一種抽簽方式使第k個(gè)人可能勝出，則我們說(shuō)第k人有可能勝出，我們的任務(wù)是根據(jù)n個(gè)人的強(qiáng)弱關(guān)系，判斷可能勝出的人數(shù)。編號(hào)為x的人能從所有人中勝出，必要條件是他能與自己“相遇”，即把環(huán)看成鏈，x點(diǎn)拆成兩個(gè)在這條鏈的兩端，中間的人全部被淘汰出局，x保持不敗。這樣，在連續(xù)幾個(gè)人的鏈中，只須考慮頭尾兩個(gè)人能否勝利會(huì)師，中間的則不予考慮，從而少了一維狀態(tài)表示量。設(shè)meet[i,j]記錄i和j能否相遇，能相遇則為true，否則為false。狀態(tài)轉(zhuǎn)移方程為若圖片看不了則：F[I,j]=(f[I,k]andf[k,j])and(e[I,k]ore[j,k]),i<k<j小H的小屋【問題描述】小H發(fā)誓要做21世紀(jì)最偉大的數(shù)學(xué)家。他認(rèn)為，做數(shù)學(xué)家與做歌星一樣，第一步要作好包裝，不然本事再大也推不出去。為此他決定先在自己的住所上下功夫，讓人一看就知道里面住著一個(gè)“未來(lái)的大數(shù)學(xué)家”。為了描述方便，我們以向東為x軸正方向，向北為y軸正方向，建立平面直角坐標(biāo)系。小H的小屋東西長(zhǎng)為100Hil（Hil是小H自己使用的長(zhǎng)度單位，至于怎樣折合成“m”，誰(shuí)也不知道）。東墻和西墻均平行于y軸，北墻和南墻分別是斜率為k1和k2的直線，k1和k2為正實(shí)數(shù)。北墻和南墻的墻角處有很多塊草坪，每塊草坪都是一個(gè)矩形，矩形的每條邊都平行于坐標(biāo)軸。相鄰兩塊草坪的接觸點(diǎn)恰好在墻上，接觸點(diǎn)的橫坐標(biāo)被稱為它所在墻的“分點(diǎn)”，這些分點(diǎn)必須是1到99的整數(shù)。小H認(rèn)為，對(duì)稱與不對(duì)稱性的結(jié)合才能充分體現(xiàn)“數(shù)學(xué)美”。因此，在北墻角要有m塊草坪，在南墻角要有n塊草坪，并約定m≤n。如果記北墻和南墻的分點(diǎn)集合分別為X1，X2，則應(yīng)滿足X1含于X2，即北墻的任何一個(gè)分點(diǎn)一定是南墻的分點(diǎn)。由于小H目前還沒有豐厚的收入，他必須把草坪的造價(jià)降到最低，即草坪的占地總面積最小。你能編程幫他解決這個(gè)難題嗎？【輸入文件】?jī)H一行，包含4個(gè)數(shù)k1，k2，m，n。k1和k2為正實(shí)數(shù)，分別表示北墻和南墻的斜率，精確到小數(shù)點(diǎn)后第一位。m和n為正整數(shù)，分別表示北墻角和南墻角的草坪的塊數(shù)?！据敵鑫募恳粋€(gè)實(shí)數(shù)，表示草坪的最小占地總面積。精確到小數(shù)點(diǎn)后第一位?！炯s定】2≤m≤n≤100南北墻距離很遠(yuǎn)，不會(huì)出現(xiàn)南墻草坪和北墻草坪重疊的情況【樣例輸入】0.50.224【樣例輸出】3000.0【評(píng)分標(biāo)準(zhǔn)】對(duì)于每個(gè)測(cè)試點(diǎn)，如果你的結(jié)果與標(biāo)準(zhǔn)答案的誤差不超過0.1，則可以得到該測(cè)試點(diǎn)的滿分，否則得0分。樸素的動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度為O(L^2·m^2·n)，但是此題恰好可以卡過。

首先預(yù)處理g[k][i]即把東西長(zhǎng)度為k的區(qū)域分給南墻，分成i塊的最小面積。

可以輕易得出g[k][i]=g[k`][i-1]+(k-k`)^2*K2(k`<k)。

然后在計(jì)算f[k][i][j]即把東西長(zhǎng)度為k的區(qū)域分給南北兩邊的墻，北墻分成i塊，南墻分成j塊的最小面積。

則有：f[k][i][j]=f[k`][i-1][j`]+g[k-k`][j-j`](k`<k,j`<j)

最后的答案就是f[100][m][n]?？梢园l(fā)現(xiàn)之前的方程具有決策單調(diào)性。

也就是說(shuō)，f[k][i][j]的決策k`、j`一定不小于f[k][i-1][j]的決策k``、j``，

那么每次枚舉k`、j`的時(shí)候就可以從k``、j``開始枚舉。

這樣可以把時(shí)間復(fù)雜度降到O(L^2·m·n)。F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);多邊形-討論的動(dòng)態(tài)規(guī)劃

多角形是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)N個(gè)頂點(diǎn)的多邊形。如圖，這里N=4。每個(gè)頂點(diǎn)有一個(gè)整數(shù)標(biāo)記，每條邊上有一個(gè)“+”號(hào)或“*”號(hào)。邊從1編號(hào)到N。第一步，一條邊被拿走；隨后各步包括如下：選擇一條邊E和連接著E的兩個(gè)頂點(diǎn)V1和V2；得到一個(gè)新的頂點(diǎn)，標(biāo)記為V1與V2通過邊E上的運(yùn)算符運(yùn)算的結(jié)果。最后，游戲中沒有邊，游戲的得分為僅剩余的一個(gè)頂點(diǎn)的值。當(dāng)OP=‘+’Fmax(i,j)=max{fmax(i,k)+fmax(k+1,j)}Fmin(i,j)=min{fmin(i,k)+fmin(k+1,j)}當(dāng)OP=‘*’括號(hào)序列方塊消除(poj1390)Jimmy最近迷上了一款叫做方塊消除的游戲.游戲規(guī)則如下：n個(gè)帶顏色方格排成一列，相同顏色的方塊連成一個(gè)區(qū)域（如果兩個(gè)相鄰的方塊顏色相同，則這兩個(gè)方塊屬于同一個(gè)區(qū)域).游戲時(shí)，你可以任選一個(gè)區(qū)域消去.設(shè)這個(gè)區(qū)域包含的方塊數(shù)為x,則將得到x^2的分值.方塊消去之后，右邊的方格將向左移動(dòng).雖然游戲很簡(jiǎn)單，但是要得到高分也不是很容易.Jimmy希望你幫助他找出最高可以得到多少分.f[i,i-1,0]:=0f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),f[i,p,k+len[j]]+f[p+1,j-1,0]}ans:=f[1,m,0]四坐標(biāo)dp（平面、地圖）免費(fèi)餡餅（模型轉(zhuǎn)化）NOI1998F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];{可以忽略F[k,i,j]:=max{f[k-1,i,p]+1}j-b[k]<=p<=j;——加單調(diào)隊(duì)列優(yōu)化的。}方格取數(shù)子矩陣問題數(shù)字三角形打磚塊滑雪城堡祝福街道路徑條數(shù)棋盤切割一、問題描述將一個(gè)８×８的棋盤進(jìn)行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進(jìn)行)允許的分割方案 不允許的分割方案原棋盤上每一格有一個(gè)分值，一塊矩形棋盤的總分為其所含各格分值之和?，F(xiàn)在需要把棋盤按上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方差最小。均方差，其中平均值，xi為第i塊矩形棋盤的總分。請(qǐng)編程對(duì)給出的棋盤及n，求出的最小值。輸入第1行為一個(gè)整數(shù)n(1<n<15)。第2行至第9行每行為8個(gè)小于100的非負(fù)整數(shù)，表示棋盤上相應(yīng)格子的分值。每行相鄰兩數(shù)之間用一個(gè)空格分隔。輸出僅一個(gè)數(shù)，為（四舍五入精確到小數(shù)點(diǎn)后三位）。樣例輸入31111111311111111111111111111111111111111111111111111111011111103樣例輸出1.633二、初步分析本題的實(shí)質(zhì)是求一種最優(yōu)的棋盤分割方式，使得每塊棋盤與平均值的差值之和最小。首先我們必須明確幾個(gè)條件（關(guān)鍵字），這樣對(duì)我們理解題意進(jìn)而采取正確的算法解決問題大有幫助：均方差：在實(shí)際編程的過程中，由于n是定值，實(shí)際只需求（Xi-X）的和的值作為參數(shù)，以此簡(jiǎn)化程序的計(jì)算及存儲(chǔ)的空間。本題提供固定的８×８棋盤，并不算大，這是本題有解的重要條件，并且給我們一個(gè)暗示：以棋盤格子為存儲(chǔ)單位，將有很大的自由度。 于是我們開始考慮算法：對(duì)比八皇后問題的復(fù)雜度，我們不難看出這道題需要搜索更多的內(nèi)容，在時(shí)間上搜索算法實(shí)不可取；因此，只能使用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)本題。經(jīng)過分析，不難發(fā)現(xiàn)本題符合最優(yōu)化原理：即若第i次分割為最佳分割，則第i-1次分割為且必為最佳；定義函數(shù)F[i,j][i’,j’]為[i,j]、[i’,j’]分別為左上、右下角的棋盤的最優(yōu)值，F(xiàn)0[i,j][i’,j’]為[i,j]、[i’,j’]分別為左上、右下角的棋盤值，探尋函數(shù)F[i,j][i’,j’]的動(dòng)態(tài)轉(zhuǎn)移方程。 下面分析分割方式。當(dāng)我們進(jìn)行第i次分割時(shí)不外乎以下四種方式： 逐一進(jìn)行分析：（圖3.4-3）橫割方式：第i次切割將棋盤分為上i-1個(gè)棋盤和下1個(gè)棋盤（圖（a））A1=F0[i1,j1][i’,j2]+F[i’+1,j1][i2,j2]第i次切割將棋盤分為下i-1個(gè)棋盤和上1個(gè)棋盤（圖（b））A2=F[i1,j1][i’,j2]+F0[i’+1,j1][i2,j2]豎割方式：第i次切割將棋盤分為右i-1個(gè)棋盤和左1個(gè)棋盤（圖（c））A3=F[i1,j1][i2,j’]+F0[i1,j’+1][i2,j2]第i次切割將棋盤分為左i-1個(gè)棋盤和右1個(gè)棋盤（圖（d））A3=F0[i1,j1][i2,j’]+F[i1,j’+1][i2,j2]狀態(tài)轉(zhuǎn)移方程為F[i1,j1][i2,j2]=min{A1,A2,A3,A4}(1<=i1,j1<=8,i1<=i2<=8,j1<=j2<=8,2<=k<=n)其中k代表分割的棋盤數(shù)，單調(diào)遞增，因此第k次分割只與k-1次的結(jié)果有關(guān)，所以每做完第k次對(duì)棋盤的規(guī)劃F0F。由此節(jié)省下許多空間。三、程序?qū)崿F(xiàn) 下面我們討論程序?qū)崿F(xiàn)的具體步驟與代碼的優(yōu)化。 首先在讀入過程段我們進(jìn)行準(zhǔn)備工作，累加計(jì)算出F0并統(tǒng)計(jì)出棋盤每個(gè)格子值之和S來(lái)計(jì)算平均數(shù)Average。s0;fori:=1to8doforj:=1to8dobegin read(f[i,j][i,j]);ss+f[i,j][i,j]; {讀入棋盤每個(gè)格子的值，并統(tǒng)計(jì)其和} fori1:=1toido {枚舉左上方坐標(biāo)i1,j1} forj1:=1tojdo fori2:=ito8do forj2:=jto8do {枚舉右上方坐標(biāo)i2,j2} if(i1<>i)or(j1<>j)or(i2<>i)or(j2<>j) thef[i1,j1][i2,j2]f[i1,j1][i2,j2]+f[i,j][i,j]; end; 在套用循環(huán)算出F0[i1,j1][i2,j2]的值，此處不再贅述。 然后用動(dòng)態(tài)規(guī)劃求解：fori:=2tondobegin {分階段，第i次分割} fori1:=1to8do forj1:=1to8do fori2:=i1to8do forj2:=j1to8dobegin {確定坐上、右下角坐標(biāo)} F[i1,j1][i2,j2]max; fori’:=i1toi2-1dobegin 計(jì)算A1,A2； F[i1,j1][i2,j2]min{A1,A2}; end; fori’:=i1toi2-1dobegin 計(jì)算A3,A4； F[i1,j1][i2,j2]min{F[i1,j1][i2,j2],A3,A4}; end; end; F0end;顯然問題的解為三、小結(jié)本題是極有代表性的動(dòng)態(tài)規(guī)劃題型，較之NOI99的其他題目算是比較簡(jiǎn)單的。此題的思路簡(jiǎn)單而明了，沒有太多限制條件讓人梳理不清，空間的自由度很大，唯一的限制便是運(yùn)行時(shí)間。所謂窺一斑可見全豹，從本題的思考過程中，我們不難總結(jié)出應(yīng)用動(dòng)態(tài)規(guī)劃算法的一般思路及步驟：確定算法，整體估計(jì)可行度。一般從兩方面著手：時(shí)空復(fù)雜度和最優(yōu)化原理。建立模型，考慮可能出現(xiàn)的情況。建立動(dòng)態(tài)轉(zhuǎn)移方程。程序?qū)崿F(xiàn)及代碼優(yōu)化。ZOJcheese（竟然沒給數(shù)據(jù)范圍？?。┙o出一個(gè)地圖,每個(gè)點(diǎn)上有相應(yīng)數(shù)量的cheese,從(0,0)開始,每到一個(gè)格子就把這個(gè)格子里的cheese吃光,每走一步方向只能是上下左右,每一步最多的格子數(shù)為k,每一步之后的一格所包含的cheese數(shù)量要比之前一格多…怎樣才能使得所得的cheese數(shù)最多呢,輸出最多的cheese數(shù).五樹型dp選課二叉蘋果樹貪吃的九頭龍聚會(huì)的快樂皇宮看守APIO2007風(fēng)鈴訪問術(shù)館ioi2005河流先多叉轉(zhuǎn)二叉。進(jìn)行了相關(guān)的轉(zhuǎn)化之后，設(shè)f(i,j,k)表示在新樹中，以i結(jié)點(diǎn)為根的子樹中，分配k個(gè)加工廠。并且離i結(jié)點(diǎn)最近的加工廠在j結(jié)點(diǎn)的情況下。i結(jié)點(diǎn)及其子樹內(nèi)的所有產(chǎn)品，加工所需要的費(fèi)用。轉(zhuǎn)移方程很容易就可以寫出來(lái)：總時(shí)間復(fù)雜度為O(N2K2)。有向樹k中值問題給定一棵有向樹T，樹T中每個(gè)頂點(diǎn)u都有一個(gè)權(quán)w(u)；樹的每條邊(u,v)也都有一個(gè)非負(fù)邊長(zhǎng)d(u,v)。有向樹T的每個(gè)頂點(diǎn)u可以看作客戶，其服務(wù)需求量為w(u)。每條邊(u,v)的邊長(zhǎng)d(u,v)可以看作運(yùn)輸費(fèi)用。如果在頂點(diǎn)u處未設(shè)置服務(wù)機(jī)構(gòu)，則將頂點(diǎn)u處的服務(wù)需求沿有向樹的邊(u,v)轉(zhuǎn)移到頂點(diǎn)v處服務(wù)機(jī)構(gòu)需付出的服務(wù)轉(zhuǎn)移費(fèi)用為w(u)*d(u,v)。樹根處已設(shè)置了服務(wù)機(jī)構(gòu)，現(xiàn)在要在樹T中增設(shè)k處服務(wù)機(jī)構(gòu)，使得整棵樹T的服務(wù)轉(zhuǎn)移費(fèi)用最小。對(duì)于給定的有向樹T，編程計(jì)算在樹T中增設(shè)k處服務(wù)機(jī)構(gòu)的最小服務(wù)轉(zhuǎn)移費(fèi)用。先轉(zhuǎn)化成二叉樹，然后dp。f[x,u,j]（以x為根的子樹到u的最小費(fèi)用）=min{f[lc[x],u,i]+f[rc[x],u,j-i]+w[x]*d[x,u],f[lc[x],x,i]+f[rc[x],u(想想轉(zhuǎn)二叉樹)，j-i-1]}，同ioi2005河流。記憶化搜索遞規(guī)求解。至于獨(dú)立中值，只有一點(diǎn)不同，自己想吧。NOI2006網(wǎng)絡(luò)收費(fèi)NOI2006千年蟲NOI2003逃學(xué)的小孩問題抽象本題題意很明確，即在一棵樹中，每條邊都有一個(gè)長(zhǎng)度值，現(xiàn)要求在樹中選擇3個(gè)點(diǎn)X、Y、Z，滿足X到Y(jié)的距離不大于X到Z的距離，且X到Y(jié)的距離與Y到Z的距離之和最大，求這個(gè)最大值。很顯然，該題的結(jié)構(gòu)模型是一棵樹，而且數(shù)據(jù)量很大，很容易把這題的方法向在樹形結(jié)構(gòu)上使用動(dòng)態(tài)規(guī)劃上靠攏?？紤]任意節(jié)點(diǎn)a時(shí)，很容易發(fā)現(xiàn)，如果以這個(gè)點(diǎn)作為題目中要求的節(jié)點(diǎn)Y，那么只需要求出離這點(diǎn)最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)即可。但是在樹形結(jié)構(gòu)上，計(jì)算出離某個(gè)節(jié)點(diǎn)最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)需要的復(fù)雜度，而我們并不知道哪個(gè)點(diǎn)是答案中的節(jié)點(diǎn)Y，所以必須枚舉這個(gè)點(diǎn)，這樣一來(lái)，時(shí)間復(fù)雜度就成了，在N=200000時(shí)會(huì)嚴(yán)重超時(shí)，因此這個(gè)方法是不可行的。枚舉Y點(diǎn)的話，會(huì)超時(shí)，是否就無(wú)法加上枚舉的思想呢？可以多嘗試一些思路。觀察這樣一棵樹：21321346751038453可以把點(diǎn)3當(dāng)作點(diǎn)X，點(diǎn)1當(dāng)作點(diǎn)Y，點(diǎn)6當(dāng)作點(diǎn)Z，這樣就可以得到最大值了。因?yàn)閨XY|=|YX|，故只需考慮YX和YZ這兩條路就可以了。在圖中來(lái)觀察這兩條路，可以發(fā)現(xiàn)分別是這樣走的：YX：123，YZ：1246。來(lái)比較這兩條路的行程，可以發(fā)現(xiàn)，都是從1先到2，然后再分開走各自的路，而且滿足從2以后的經(jīng)過的節(jié)點(diǎn)，沒有重復(fù)的節(jié)點(diǎn)。為了方便，我們形象地將點(diǎn)2稱為分叉點(diǎn)。如果枚舉分叉點(diǎn)，能不能得到一個(gè)高效的算法呢？來(lái)嘗試分析這種想法。枚舉分叉點(diǎn)將某個(gè)點(diǎn)a當(dāng)作分叉點(diǎn)時(shí)，以其為根構(gòu)造一棵樹，對(duì)節(jié)點(diǎn)Y，就有兩種情況：eq\o\ac(○,1)Y就是節(jié)點(diǎn)a；eq\o\ac(○,2)Y在a的某個(gè)孩子節(jié)點(diǎn)的子樹上。對(duì)于情況1，可以把它轉(zhuǎn)化為情況2，只需給a加一個(gè)空的孩子節(jié)點(diǎn)，認(rèn)為它和a之間的距離是0即可。既然a是分叉點(diǎn)，那么X和Z就不能在同一棵子樹上，X和Y，Y和Z也不能在同一棵子樹上。題目中要求的是使|XY|+|YZ|最大，也就是要求2|Ya|+|Za|+|Xa|最大。至此，思路已完全明確，對(duì)于以a為分叉點(diǎn)的情形，只需求出到a的最遠(yuǎn)的3個(gè)點(diǎn)，而且這3個(gè)點(diǎn)分別處于a的3棵不同的子樹之中。如果采用枚舉分叉點(diǎn)的方法的話，每次都需要的計(jì)算才行，時(shí)間復(fù)雜度就又成了。兩次遍歷這里，需要改變一下思路。以點(diǎn)1為根，計(jì)算出要求的值后，不去枚舉其它的節(jié)點(diǎn)，而把這棵樹再遍歷一遍，進(jìn)行一次BFS，深度小的先訪問，深度大的后訪問，就保證了訪問到某一個(gè)節(jié)點(diǎn)的時(shí)候，其父親節(jié)點(diǎn)已經(jīng)被訪問過了。假設(shè)我們現(xiàn)在訪問到了點(diǎn)a，我們現(xiàn)在要求的是距點(diǎn)a的3個(gè)最遠(yuǎn)的點(diǎn)，且這3個(gè)點(diǎn)到a的路徑上不經(jīng)過除a外的相同節(jié)點(diǎn)。顯然，這3個(gè)點(diǎn)要么位于以a為根的子樹中，要么位于以a為根的子樹外。如果在以a為根的子樹外，那么是一定要通過a的父親節(jié)點(diǎn)與a相連的。至此，思路逐漸清晰起來(lái)。此次遍歷時(shí)，對(duì)于點(diǎn)a，檢查其父親節(jié)點(diǎn)，只需求出到其父親節(jié)點(diǎn)的最遠(yuǎn)的，且不在以a為根的子樹中的那點(diǎn)即可，再與第一次遍歷求得的值進(jìn)行比較，就可以求出以該點(diǎn)為分叉點(diǎn)時(shí)，|XY|+|YZ|的最大值了。具體方法為，每個(gè)點(diǎn)記錄最大的兩個(gè)值，并記錄這最大的兩個(gè)值分別是從哪個(gè)相鄰節(jié)點(diǎn)傳遞來(lái)的。當(dāng)遍歷到其某個(gè)孩子節(jié)點(diǎn)時(shí)，只需檢查最大值是否是從該孩子節(jié)點(diǎn)傳遞來(lái)的，如果是，就取次大值，如果不是，就可以取最大值。這樣一來(lái)，該算法的時(shí)間復(fù)雜度和空間復(fù)雜度都為，是個(gè)非常優(yōu)秀的算法。注意這里提醒大家注意一點(diǎn)，計(jì)算過程中的值和最后的結(jié)果可能會(huì)超過長(zhǎng)整型的范圍，所以這里需要使用int64或者double類型。對(duì)于樹必須進(jìn)行兩次遍歷，才能求得最終的最大值。該例題的分析中提出了分叉點(diǎn)的想法，是比較具有創(chuàng)造性的，需要從多個(gè)角度思考。因此，在平時(shí)的練習(xí)中，當(dāng)對(duì)一道題目束手無(wú)策時(shí)，可從多個(gè)角度思考，創(chuàng)造新思維，使題目得到解決。此題遍歷兩次的方法具有普遍性，在許多題目中都可以得到應(yīng)用：記錄最大的兩個(gè)值，并記錄是從哪個(gè)節(jié)點(diǎn)傳遞來(lái)的思想方法。這種遍歷兩次和記錄最大的多個(gè)值的思想是值得學(xué)習(xí)的，也是動(dòng)態(tài)規(guī)劃在樹上進(jìn)行使用的經(jīng)典方法。本題的樹型動(dòng)態(tài)規(guī)劃復(fù)雜度是線形的，但是也有一部分問題，在線形的時(shí)間內(nèi)無(wú)法出解。這類問題的變化更多，從狀態(tài)的確立到狀態(tài)的轉(zhuǎn)移，都對(duì)思考角度有著更高的要求。六字符串dpNOI2000古城之謎古城之謎Ural1002Phoneifexist(copy(s,j,i-j))thenf[i]:=min(f[i],f[j]+1);字符串匹配（通配符問題）字符串通配（**——）給一個(gè)帶通配符*和?的字符串S，問它能不能匹配字符串T。例如，a*b?能夠匹配aabc，但是不能匹配aab其中*能夠匹配0個(gè)或任意多個(gè)字符；？匹配1個(gè)任意字符！思路:列表aabc

a

b

c

a

1

0

0

*

1

1

1

b

0

1

0

?

0

0

1

*1111b0010?0001aaba110*111b001?000本格"?":左上為1則本格為1"*":前一行上為1則本格為1,左為1則本格為1字母:行列上的字母相同且左上為1,則本格為1問題：如果T也可以包含通配符呢？以f[I,j]=true表示S串中的前I個(gè)和串T中的前j個(gè)能完全匹配;=false表示不能完全匹配對(duì)于兩串都有通配符的問題，我認(rèn)為應(yīng)該是：if(S[I]=’*’orT[j]=’*’)and(f[I-1,j]orf[I,j-1])thenf[I,j]=trueelseif((S[I]=’?’)or(T[j]=’?’)or(S[I]=T[j]))andf[I-1,j-1]thenf[I,j]=trueelsef[I,j]=false;求大神確認(rèn)?。∑哓澬膁p快餐問題一、問題描述Peter最近在R市開了一家快餐店，為了招攬顧客，該快餐店準(zhǔn)備推出一種套餐，該套餐由A個(gè)漢堡，B個(gè)薯?xiàng)l和C個(gè)飲料組成。價(jià)格便宜。為了提高產(chǎn)量，Peter從著名的麥當(dāng)勞公司引進(jìn)了N條生產(chǎn)線。所有的生產(chǎn)線都可以生產(chǎn)漢堡，薯?xiàng)l和飲料，由于每條生產(chǎn)線每天所能提供的生產(chǎn)時(shí)間是有限的、不同的，而漢堡，薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間又不同。這使得Peter很為難，不知道如何安排生產(chǎn)才能使一天中生產(chǎn)的套餐產(chǎn)量最大。請(qǐng)你編一程序，計(jì)算一天中套餐的最大生產(chǎn)量。為簡(jiǎn)單起見，假設(shè)漢堡、薯?xiàng)l和飲料的日產(chǎn)量不超過100個(gè)。輸入：輸入文件共四行。第一行為三個(gè)不超過100的正整數(shù)A、B、C中間以一個(gè)空格分開。第三行為3個(gè)不超過100的正整數(shù)p1,p2,p3分別為漢堡，薯?xiàng)l和飲料的單位生產(chǎn)耗時(shí)。中間以一個(gè)空格分開。第三行為N(0<=0<=10)，第四行為N個(gè)不超過10000的正整數(shù)，分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時(shí)間，中間以一個(gè)空格分開。

輸出:每天套餐的最大產(chǎn)量。資源分配型dp。算法1：四維純DP較容易想到的方程是：F[I,j,k,L]:=f[i-1,j-j0,k-k0,L-L0]andg[I,j0,k0,L0]F[I,j,k,L]表示前i條生產(chǎn)線能否生產(chǎn)出j個(gè)漢堡、k個(gè)薯?xiàng)l、L個(gè)飲料。g[I,j0,k0,L0]表示第i條生產(chǎn)線能否生產(chǎn)出j0個(gè)漢堡、k0個(gè)薯?xiàng)l、L0個(gè)飲料。Ans=max{min{jdiva,kdivb,Ldivc}|f[n,j,k,L]=true}空間不會(huì)暴，但時(shí)間復(fù)雜度為：O（n*100^6）無(wú)法承受！V_V算法2：三維純DPF[I,j,k]表示前I條生產(chǎn)線生產(chǎn)j個(gè)漢堡，k個(gè)薯?xiàng)l的情況下最多生產(chǎn)飲料的個(gè)數(shù)。g[I,j,k]表示第I條生產(chǎn)線生產(chǎn)j個(gè)漢堡，k個(gè)薯?xiàng)l的情況下最多生產(chǎn)飲料的個(gè)數(shù)。復(fù)雜度為O（n*100^4），還需進(jìn)一步優(yōu)化！上限優(yōu)化：利用條件“漢堡、薯?xiàng)l和飲料的日產(chǎn)量不超過100個(gè)”優(yōu)化上限；根據(jù)每條生產(chǎn)線的生產(chǎn)能力局部?jī)?yōu)化關(guān)于g[I,j,k]的枚舉上限（即5個(gè)for循環(huán)中的后兩個(gè)循環(huán)的上限）。算法3：greed+DPDP之前，根據(jù)條件“漢堡、薯?xiàng)l和飲料的日產(chǎn)量不超過100個(gè)”，用貪心法求極限解，若極限解可行則輸出并退出程序。青蛙過河此題方程容易寫出：ifI處有石頭F[i]:=min{f[k]}+1(i-t<=k<=i-s)；ifI處無(wú)石頭f[i]:=min{f[k]}(i-t<=k<=i-s)復(fù)雜度為O（L*（t-s）），無(wú)法過！優(yōu)化：對(duì)于長(zhǎng)度大于s*t且無(wú)石頭的一段，可以縮短變?yōu)閟*t，因?yàn)閷?duì)于任意長(zhǎng)度大于或等于s*t無(wú)石頭的橋，總可以找到一種方法，能從橋的一端正好跳到另一端。（啟示：尋找冗余以求優(yōu)化）證明：對(duì)于len=st+k(k>0)，若s+k<=t,len=(t-1)s+(s+k);若t<s+k<=2t-s即0<s+k-t<=t-s,len=(t-2)s+[s+(s+k-t)]+t;若2t-s<s+k<=3t-2s即0<(2s+k-2t)<=t-s,len=(t-3)s+[s+(2s+k-2t)]+2t;……若(t-1)t-(t-2)s<s+k<=t^2-(t-1)s即0<(t-1)s+k-(t-1)t<=t-sLen={s+[(t-1)s+k-(t-1)t]}+(t-1)t;由最后一個(gè)式子知，若s+k再大，則len>t^2，而t^2=(s+t-s)t=st+(t-s)t，故此時(shí)len=(t-s)t+st+kk(kk>0)，又回到了最初的分析！——心血啊……八多進(jìn)程dpCEOI2005serviceservice，3

sec，64mb

一個(gè)公司有三個(gè)移動(dòng)服務(wù)員。如果某個(gè)地方有一個(gè)請(qǐng)求，某個(gè)員工必須趕到那個(gè)地方去（那個(gè)地方?jīng)]有其他員工）某一時(shí)刻只有一個(gè)員工能移動(dòng)。被請(qǐng)求后，他才能移動(dòng)，不允許在同樣的位置出現(xiàn)兩個(gè)員工。從p到q移動(dòng)一個(gè)員工，需要花費(fèi)c(p,q)。這個(gè)函數(shù)沒有必要對(duì)稱，但是c(p,p)=0。公司必須滿足所有的請(qǐng)求。目標(biāo)是最小化公司花費(fèi)。

輸入

第一行有兩個(gè)整數(shù)L,N(3<=L<=200,

1<=N<=1000)。L是位置數(shù)

；N是請(qǐng)求數(shù)。每個(gè)位置從1到L編號(hào)。下L行每行包含L個(gè)非負(fù)整數(shù)。第i+1行的第j個(gè)數(shù)表示c(i,j)

并且它小于2000。最后一行包含N個(gè)數(shù)，是請(qǐng)求列表。一開始三個(gè)服務(wù)員分別在位置1，2，3。

輸出

第一行包含一個(gè)數(shù)M表示最小服務(wù)花費(fèi)。第二行包含N個(gè)數(shù)，第i個(gè)數(shù)表示哪個(gè)員工執(zhí)行服務(wù)任務(wù)（1，2或3）。如果有多種可能，輸出任意一種。

樣例輸入

5

9

0

1

1

1

1

1

0

2

3

2

1

1

0

4

1

2

1

5

0

1

4

2

3

4

0

4

2

4

1

5

4

3

2

1

樣例輸出

5

1

2

1

2

2

1

3

1

3Min(f[i,j,k],f[i-1,j,k]+c[t[i-1],t])Min(f[i,t[i-1],k],f[i-1,j,k]+c[j,t])Min(f[i,j,t[i-1]],f[i-1,j,k]+c[k,t])Vijos1143三取方格數(shù)九狀壓dp炮兵陣地APIO2007動(dòng)物園題目簡(jiǎn)述：N個(gè)動(dòng)物圍成一個(gè)環(huán)，有K個(gè)小朋友，每個(gè)小朋友可以看到五個(gè)連續(xù)的動(dòng)物，每個(gè)小朋友都有自己喜歡或討厭的動(dòng)物，當(dāng)有一個(gè)自己討厭的動(dòng)物被移走或能看到一個(gè)自己喜歡的動(dòng)物時(shí)，這個(gè)小朋友就會(huì)高興。求最優(yōu)的移走動(dòng)物的方案，使得最多的小朋友高興。主要要注意的就是因?yàn)槭黔h(huán)，所以前4個(gè)點(diǎn)的狀態(tài)必須一開始固定死，以下是解題報(bào)告（來(lái)源：hereisrj）：動(dòng)態(tài)規(guī)劃，用二進(jìn)制表示動(dòng)物的取舍。F[i][j]表示從1到i+4的動(dòng)物，其中i到i+4的動(dòng)物的取舍狀態(tài)為j時(shí)，最多的高興的小朋友的數(shù)目。狀態(tài)轉(zhuǎn)移方程為:F[i][j]=max{F[i-1][(j<<1)&31],F[i-1][((j<<1)&31)|1]}+num[i][j];j的二進(jìn)制串中，最后一位表示i，倒數(shù)第二為表示i+1,以此類推。num[i][j]為看到i到i+4的動(dòng)物的小朋友在j的狀態(tài)下高興的數(shù)目；邊界條件：F[0][j]=0;目標(biāo)函數(shù)：max{F[N][j]}(0<=j<32);不過，這是環(huán)形，因此要枚舉固定開頭的4個(gè)動(dòng)物。算法分析：動(dòng)規(guī)的階段為O(2^4),狀態(tài)為O(2^5*N),狀態(tài)轉(zhuǎn)移O(1);總的時(shí)間復(fù)雜度為O(2^9*N);基本可以承受。{淺陋看法：此題還可加強(qiáng)N的范圍，這時(shí)可以按小孩逐個(gè)轉(zhuǎn)}購(gòu)物（IOI95-2） 可將每種物品按5進(jìn)制編碼。（5為每種物品數(shù)的上限）Roger游戲任務(wù)一（CTSC98Day24） 一個(gè)正方體在一個(gè)方格內(nèi)的狀態(tài)只有24種，而且可以通過頂面和前面來(lái)表示，這樣用3維的狀態(tài)(x,y,p)就可以解決，p為1到24種狀態(tài)中的一種。十判定型dp其實(shí)，這類問題歸屬遞推問題。針對(duì)一些不滿足最優(yōu)性原理的題設(shè)計(jì)。Mod4最優(yōu)路徑十一目標(biāo)型dpCEOI98subtraF[I,j]:=f[I-1,j+a]orf[i-1,j-a]積木城堡Vijos1037搭建雙塔問題多諾米骨牌垃圾陷阱十二概率dp聰聰和可可(NOI2005)題目的主要思想是動(dòng)態(tài)規(guī)劃（記憶化搜索）。設(shè)F[X,Y]表示可可在X點(diǎn)，聰聰在Y點(diǎn)時(shí)Gameover的平均步數(shù)。在已知可可位置時(shí)，聰聰?shù)囊苿?dòng)方法是題目本身規(guī)定的。不妨設(shè)G[X,Y]表示可可在X點(diǎn)，聰聰在Y點(diǎn)時(shí)，聰聰下一步移動(dòng)到的位置，而T[X]表示與X相連的點(diǎn)的個(gè)數(shù)，S[X][I]表示與X相連的第I個(gè)點(diǎn)。那么有狀態(tài)轉(zhuǎn)移方程F[X,Y]=(∑F[S[X][K],G[X,Y]]+F[X,G[X,Y]])/(T[x]+1)+1。關(guān)鍵是對(duì)G[X][Y]的初始化，用Floyed效率太低，大數(shù)據(jù)肯定超時(shí)。Heap+Dijkstra可以接受，復(fù)雜度為O（（N+E）logN）。最好的方法就是BFS。求權(quán)值為1的任兩點(diǎn)間最短路的時(shí)間復(fù)雜度為O（NE）。動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為O（N2）。整個(gè)算法的時(shí)間復(fù)雜度為O（NE）。血緣關(guān)系（妖怪家族）十三二次dp（雙重動(dòng)態(tài)規(guī)劃）基因序列（Gen.pas）Genotype

是一個(gè)有限的基因序列。它是由大寫的英文字母A-Z組成，不同的字母表示不同種類的基因。一個(gè)基因可以分化成為一對(duì)新的基因。這種分化被一個(gè)定義的規(guī)則集合所控制。每個(gè)分化的規(guī)則可以用三個(gè)大寫字母A1A2A3表示，含義為基因A1可以分化成A2A3。我們用S代表特種基因，繁殖genotype是從特種基因序列開始。根據(jù)給定的規(guī)則，它由被選擇控制規(guī)則對(duì)基因不斷進(jìn)行繁殖而成。現(xiàn)在的問題是，從文件中讀入一個(gè)定義的規(guī)則集和一個(gè)想生成的genotypes單詞序列，對(duì)每一個(gè)給定的genotype，根據(jù)給定的分化規(guī)則，檢查它是否能從某一個(gè)確定特種基因序列生成，如果能，找到最小的序列長(zhǎng)度。輸入（GEN.IN）文件的第一行有一個(gè)整數(shù)n,1<=n<=10000。下面n每一行為一個(gè)分化規(guī)則，這些規(guī)則都由包含A–Z的三個(gè)大寫字母組成。接下來(lái)有一個(gè)整數(shù)k,1<=k<=10000。接下來(lái)的k行有一個(gè)genotype，Genotype由沒有空格的單詞組成，最多100個(gè)英文大寫字母。輸出（GEN.OUT）在文件中有k行,在第I行應(yīng)寫入：一個(gè)正整數(shù)――需要生成第I個(gè)genotype的最小長(zhǎng)度；或者單詞NIE,如果不能生成對(duì)應(yīng)的genotype。輸入樣例

輸出樣例：6

3SAB

1SBC

NIESAAACABCCCBC3ABBCAAABCACCCBA解題報(bào)告：這是一道有些難度的動(dòng)態(tài)規(guī)劃題。因?yàn)樗鼉纱斡玫搅藙?dòng)態(tài)規(guī)劃，最容易想到的是用g[I]表示目標(biāo)狀態(tài)前I個(gè)字母可以轉(zhuǎn)變成的最小長(zhǎng)度，那么g[I]=min{g[j]+1}，其中a[j+1..i]是可以轉(zhuǎn)變?yōu)橐粋€(gè)S的字串。這時(shí)問題就很自然的轉(zhuǎn)到了如何確定這樣的序列。我們用f[I,j,ch]表示目標(biāo)序列的第I位到第j位可以壓縮為字母ch，那么如果存在f[I,j1,ch1]、f[j1+1,j2,ch2]，并且條件中有chch1ch2，則f[I,j,ch]=true。這樣問題就解決了。時(shí)間復(fù)雜度為O(len^3*26^2)，還是承受的起的，但是空間復(fù)雜度就較高了，所以我們有必要對(duì)狀態(tài)的表示進(jìn)行優(yōu)化。我們用一個(gè)26位的二進(jìn)制數(shù)表示狀態(tài)，這樣就只需一個(gè)長(zhǎng)整型的數(shù)即可表示狀態(tài)。此題的解決是一步步倒推得到的?？荚嚂r(shí)這種思考方式非常重要。只要抓住了題目的本質(zhì)，理清思路就可以解決問題。consts:array['A'..'Z']ofinteger=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26);

varf:array[1..100,1..100]oflongint;

i,j,l,k,n,len,c1,c2:integer;

g:array[1..26,1..26]oflongint;

c:Array[0..100]ofinteger;

st:string;

procedureinit;

begin

assign(input,'gen.in');reset(input);

readln(n);

fori:=1tondo

begin

readln(st);

g[s[st[2]],s[st[3]]]:=g[s[st[2]],s[st[3]]]+1shl(s[st[1]]-1);//G[i,j]用二進(jìn)制表示字符i,j能轉(zhuǎn)化到的字符

end;

end;

proceduredp;

begin

len:=length(st);

fori:=1tolendo

forj:=1tolendof[i,j]:=0;

//F[i,j]用二進(jìn)制表示字符的第i位到第j位能轉(zhuǎn)化到的字符

fori:=1tolendof[i,i]:=1shl(s[st[i]]-1);

//i=j的情況

fori:=1tolen-1dof[i,i+1]:=g[s[st[i]],s[st[i+1]]];

//i+1=j的情況

forL:=3tolendo

//長(zhǎng)度

fori:=1tolen-L+1do

//起始i

forj:=itoi+L-2do

//枚舉分割點(diǎn)

forc1:=1to26do

if(f[i,j]and(1shl(c1-1))>0)then

forc2:=1to26do

if(f[j+1,i+L-1]and(1shl(c2-1))>0)then

//兩段分別能達(dá)到c1,c2

f[i,i+L-1]:=f[i,i+L-1]org[c1,c2];

//集合的合并

fori:=1tolendoc[i]:=0;

c[0]:=1;

fori:=1tolendo

forj:=0toi-1do

if(c[j]<>0)and(f[j+1,i]and(1shl18)>0)and((c[i]=0)or(c[i]>c[j]+1))then

c[i]:=c[j]+1;

//C[i]表示前i個(gè)字符轉(zhuǎn)化為'S'的最少個(gè)數(shù)

ifc[len]=0thenwriteln('NIE')elsewriteln(c[len]-1);

end;

proceduremain;

vari:integer;

begin

readln(k);

fori:=1tokdo

begin

readln(st);

dp;

end;

end;

begin

init;

assign(output,'gen.out');rewrite(output);

main;

close(input);close(output);

end.此處狀壓，妙！鄙人認(rèn)為此題歸屬“區(qū)間dp”+二次dp小胖辦證（買票）樹中各點(diǎn)的最遠(yuǎn)點(diǎn)城市交通（似乎還可以拆點(diǎn)求最短路）十四遞推問題核電站問題

一個(gè)核電站有N個(gè)放核物質(zhì)的坑，坑排列在一條直線上。如果連續(xù)M個(gè)坑中放入核物質(zhì)，則會(huì)發(fā)生爆炸，于是，在某些坑中可能不放核物質(zhì)。

任務(wù)：對(duì)于給定的N和M，求不發(fā)生爆炸的放置核物質(zhì)的方案總數(shù)。Input

該題有多組測(cè)試數(shù)據(jù)，每組數(shù)據(jù)一行，兩個(gè)正整數(shù)N，M(1＜N＜50，2≤M≤5)Output

每組數(shù)據(jù)只輸出一個(gè)正整數(shù)S，表示方案總數(shù)。SampleInput

43SampleOutput

13fori:=m+1tondoa[i]:=2*a[i-1]-a[i-m-1];數(shù)的劃分情書抄寫員錯(cuò)位排列f:=(i-1)(f[i-2]+f[i-1]);f[n]:=n*f[n-1]+(-1)^(n-2);直線分平面最大區(qū)域數(shù)f[n]:=f[n-1]+n:=n*(n+1)div2+1;折線分平面最大區(qū)域數(shù)f[n]:=(n-1)(2*n-1)+2*n;凸多邊形分三角形方法數(shù)f[n]:=C(2*n-2,n-1)divn;對(duì)于k邊形f[k]:=C(2*k-4,k-2)div(k-1);//(k>=3)二叉樹數(shù)出棧序列 在原始序列中有i個(gè)數(shù)，堆棧中有j個(gè)數(shù)時(shí)的，通過pop和push操作能得到的序列數(shù)，定義為f[i,j]，則本題求的是f[n,0]。 f[i,j]=f[i-1,j+1]+f[i,j-1]{push操作+pop操作} f[0,1..n]=1 f[1..n,-1]=0 Catalan數(shù)列一般形式1,1,2,5,14,42,132f[n]:=C(2k,k)div(k+1);彩燈布置有n盞位置固定的彩燈排列成圓形，要用m種顏色去著色，求使相鄰的彩燈著不同顏色的方案數(shù)。f(n)=(m-2)*f(n-1)+(m-1)*f(n-2)盒子與球現(xiàn)有r個(gè)互不相同的盒子和n個(gè)互不相同的球，要將這n個(gè)球放入r個(gè)盒子中，且不允許有空盒子。問有多少種方法？例如：有2個(gè)不同的盒子（分別編為1號(hào)和2號(hào)）和3個(gè)不同的球（分別編為1、2、3號(hào)），則有6種不同的方法：1號(hào)盒子1號(hào)球1、2號(hào)球1、3號(hào)球2號(hào)球2、3號(hào)球3號(hào)球2號(hào)盒子2、3號(hào)球3號(hào)球2號(hào)球1、3號(hào)球1號(hào)球1、2號(hào)球輸入格式InputFormat兩個(gè)整數(shù)，n和r，中間用空格分隔。（0≤n,r≤10）輸出格式OutputFormatN臢樣例輸入SampleInput32樣例輸出SampleOutput6f[i,1]:=1;f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);另一種解法：盒子相同，球不同的問題,并且盒子不允許有空用f[i][j]表示i個(gè)小球放入放入前j個(gè)盒子的不同方法。那么遞推公式應(yīng)該是

F[I][J]=F[I-1][J]*j+f[I-1][J-1]；解釋一下：把i個(gè)小球放入j個(gè)盒子的方案總數(shù)等價(jià)于第j個(gè)盒子本來(lái)是空的，把第i個(gè)小球放入（f[i-1][j-1]），或者是原來(lái)前j個(gè)盒子每個(gè)盒子都不是空的，那么根據(jù)乘法原理應(yīng)該有(f[i-1][j]*j)的方案總數(shù)。盒子相同而球不同的方案，這道題目把它改成了球也不同，盒子也不同了。實(shí)際上，我們?cè)谟龅竭@道題目的時(shí)候可以假設(shè)一下，假設(shè)箱子相同，那么最后的答案會(huì)是多少？求出了這個(gè)答案，最后只要乘以一個(gè)箱子的全排列也就ok了Josephus問題的數(shù)學(xué)方法摘自：/view/213217.html?fromTaglist我們知道第一個(gè)人(編號(hào)一定是(m-1)modn)出列之后，剩下的n-1個(gè)人組成了一個(gè)新的約瑟夫環(huán)（以編號(hào)為k=mmodn的人開始）:kk+1k+2...n-2,n-1,0,1,2,...k-2并且從k開始報(bào)0?，F(xiàn)在我們把他們的編號(hào)做一下轉(zhuǎn)換：k-->0k+1-->1k+2-->2......k-2-->n-2k-1-->n-1變換后就完完全全成為了(n-1)個(gè)人報(bào)數(shù)的子問題，假如我們知道這個(gè)子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況的解嗎？??！變回去的公式很簡(jiǎn)單，相信大家都可以推出來(lái)：x'=(x+k)modn如何知道(n-1)個(gè)人報(bào)數(shù)的問題的解？對(duì)，只要知道(n-2)個(gè)人的解就行了。(n-2)個(gè)人的解呢？當(dāng)然是先求(n-3)的情況----這顯然就是一個(gè)倒推問題！好了，思路出來(lái)了，下面寫遞推公式：令f表示i個(gè)人玩游戲報(bào)m退出最后勝利者的編號(hào)，最后的結(jié)果自然是f[n]遞推公式f[1]=0;f=(f+m)modi;(i>1)有了這個(gè)公式，我們要做的就是從1-n順序算出f的數(shù)值，最后結(jié)果是f[n]。因?yàn)閷?shí)際生活中編號(hào)總是從1開始，我們輸出f[n]+1由于是逐級(jí)遞推，不需要保存每個(gè)f，程序也是異常簡(jiǎn)單：pascalvarn,m,i,s:integer;beginwrite('NM=');read(n,m);fori:=2tondos:=(s+m)modi;writeln('Thewinneris',s+1);end.排列DP*1*逆序?qū)€(gè)數(shù)為k的排列數(shù)：f[I,j]表示i排列中逆序個(gè)數(shù)為j的排列數(shù)，f[i][j]=k=j-ij或者f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-i-1]*2*Ysqpf用斐波那契數(shù)列做的背景，其實(shí)和它沒一點(diǎn)關(guān)系，就是問你用n個(gè)不同數(shù)去構(gòu)一個(gè)長(zhǎng)度為p的數(shù)列的不