動(dòng)態(tài)規(guī)劃入門zyy并無(wú)卵用的起源1951年美國(guó)數(shù)學(xué)家R．Bellman等人，根據(jù)一類多階段問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。與此同時(shí)，他提出了解決這類問(wèn)題的“最優(yōu)化原理”(Principleofoptimality)：“一個(gè)過(guò)程的最優(yōu)決策具有這樣的性質(zhì)：即無(wú)論其初始狀態(tài)和初始決策如何，其今后諸策略對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)的過(guò)程而言，必須構(gòu)成最優(yōu)策略”。簡(jiǎn)言之，一個(gè)最優(yōu)策略的子策略，對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。裝做是重點(diǎn)的部分以上都是廢話。。?？偨Y(jié)一下，就是從一個(gè)初始狀態(tài)通過(guò)若干次的轉(zhuǎn)移得到問(wèn)題所需的最終狀態(tài)。問(wèn)題中的狀態(tài)必須滿足最優(yōu)；問(wèn)題中的狀態(tài)必須滿足無(wú)后效性。所謂的無(wú)后效性是指：“下一時(shí)刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無(wú)關(guān)，當(dāng)前的狀態(tài)是對(duì)以往決策的總結(jié)”。裝做是重點(diǎn)的部分以上還是廢話。。。DP主要還要在題目中感受。經(jīng)典模型I最長(zhǎng)不下降子序列給出N個(gè)數(shù)，求出其最長(zhǎng)不下降子序列的長(zhǎng)度30%(N<1000)100%(N<100000)經(jīng)典模型I30%應(yīng)該都會(huì)吧。。。f[n]表示以n結(jié)尾的最長(zhǎng)不下降子序列的長(zhǎng)度最長(zhǎng)為多少。轉(zhuǎn)移：f[i]=max(f[j])+1(a[j]<=a[i]&&j<i)復(fù)雜度：O(n^2)經(jīng)典模型I100%因?yàn)檫@里的數(shù)據(jù)范圍比較大，用經(jīng)典的n^2做法肯定會(huì)超時(shí)，所以需要一種更加高效的DP。用f[n]表示最長(zhǎng)不下降子序列長(zhǎng)度為n的序列末尾最小值為多少。然后我們轉(zhuǎn)移的時(shí)候就可以二分，二分最長(zhǎng)不下降子序列的長(zhǎng)度，然后與f[mid]比較，得出答案。用答案更新f數(shù)組。復(fù)雜度：O(nlogn)經(jīng)典模型II背包問(wèn)題給定N個(gè)物品，每個(gè)物品有一個(gè)重量和價(jià)值，你現(xiàn)在有一個(gè)大小為M的背包，問(wèn)你最多可以裝多少價(jià)值的物品，每個(gè)物品只能用一次100%(0<N,M<3000)MemoryLimit：30%128MB100%3MB經(jīng)典模型II也是一個(gè)很經(jīng)典的問(wèn)題用f[i][j]表示前i個(gè)物品使用了j的空間的最大收益轉(zhuǎn)移方程:f[i][j]=max(f[i-1][j-cost[i]]+val[i],f[i][j])但是對(duì)于100%的內(nèi)存限制如果數(shù)組開滿O(N*M)顯然是會(huì)MLE的，所以我們可以對(duì)第一維滾存，空間就變成O(M)了。經(jīng)典模型III另一種背包問(wèn)題有N種物品，每種物品的數(shù)量為C1，C2......Cn。從中任選若干件放在容量為W的背包里，每種物品的體積為W1，W2......Wn（Wi為整數(shù)），與之相對(duì)應(yīng)的價(jià)值為P1,P2......Pn（Pi為整數(shù)）。求背包能夠容納的最大價(jià)值。30%1

<=

Ci

<=

10100%1

<=

Ci

<=

200對(duì)于所有數(shù)據(jù)1

<=

N

<=

100，1

<=

W

<=

20000，對(duì)于所有數(shù)據(jù)1

<=

Wi，Pi

<=

10000經(jīng)典模型III我相信你們會(huì)30%做法。。。由于這里空間太小寫不下就不贅述了。這里100%可以用多重背包拆成01背包求解的思想，不過(guò)在拆的時(shí)候不能將Cn拆成1+1+1+1+1+1.....+1的形式。這么做會(huì)超時(shí)。應(yīng)該將Cn拆成Cn=1+2+4+8+...+(Cn-sum)。

這里sum表示前面的數(shù)字之和，例如按照規(guī)律加到第m個(gè)數(shù)，發(fā)現(xiàn)已經(jīng)大于Cn，那么sum就表示從1+2+4+8+.....+2^(m-2)。

我們可以檢驗(yàn)，在[1,Cn]中任意的數(shù)我們都可以在這個(gè)序列中找到若干數(shù)相加得到。拆分結(jié)束后我們就可以按照經(jīng)典模型II的背包求解。這題寫好可以交51nod1085簡(jiǎn)單例題的講解接下來(lái)就是簡(jiǎn)單例題的講解了。。。歡迎大家來(lái)虐題。。。ExampleI雷濤同學(xué)非常的有愛(ài)心，在他的宿舍里，養(yǎng)著一只因?yàn)槭軅痪戎男∝?當(dāng)然，這樣的行為是違反學(xué)生宿舍管理?xiàng)l例的)。(…這里省略一堆廢話，大意是貓?jiān)诳词磷訕洹?在校園里，有許多柿子樹，在雷濤所在的宿舍樓前，就有N棵。并且這N棵柿子樹每棵的高度都是H。(…這里省略一堆廢話，大意是柿子熟了貓想吃…)ExampleI小貓可以從宿舍的陽(yáng)臺(tái)上跳到窗外任意一棵柿子樹的樹頂。之后，她每次都可以在當(dāng)前位置沿著當(dāng)前所在的柿子樹向下跳1單位距離。當(dāng)然，小貓的能力遠(yuǎn)不止如此，她還可以在樹之間跳躍。每次她都可以從當(dāng)前這棵樹跳到另外的任意一棵，在這個(gè)過(guò)程中，她的高度會(huì)下降Delta單位距離。每個(gè)時(shí)刻，只要她所在的位置有柿子，她就可以吃掉。整個(gè)“吃柿子行動(dòng)”一直到小貓落到地面上為止。雷濤調(diào)查了所有柿子樹上柿子的生長(zhǎng)情況。他很想知道，小貓從陽(yáng)臺(tái)出發(fā)，最多能吃到多少柿子？他知道寫一個(gè)程序可以很容易的解決這個(gè)問(wèn)題，于是，現(xiàn)在你的任務(wù)就是幫助雷濤寫一個(gè)這樣的程序。ExampleI圖為N

=3,H

=10,Delta

=2的一個(gè)例子。小貓按照?qǐng)D示路線進(jìn)行跳躍，可以吃到最多的8個(gè)柿子。輸入文件的第一行有三個(gè)以空格分隔的整數(shù)，分別代表N,H,Delta接下來(lái)的N行，每行第一個(gè)整數(shù)為Ni，代表第i棵樹上的柿子數(shù)量。接下來(lái)是Ni個(gè)整數(shù)，每個(gè)整數(shù)Tij代表第i棵柿子樹的Tij高度上長(zhǎng)有一個(gè)柿子。輸出僅包含一個(gè)整數(shù)，即小貓最多吃到的柿子數(shù)。ExampleI-Sulotion這題很簡(jiǎn)單。題解與題面長(zhǎng)度完全不成正比。用f[i]表示到之前的高度為i的最大值用g[i]表示當(dāng)前層第i棵樹上的最大值然后轉(zhuǎn)移就好了來(lái)源Excalibur,2008(我也不知道是什么東西)ExampleII你有N波食物，食物有三種類型，你有兩只雞，每次你獲得一波食物后可以選擇一只雞喂給他，一只雞吃完后獲得的興奮值為：這次食物與前兩次食物中，類型不同的食物的種數(shù)，現(xiàn)在給你食物的類型，讓你求你最多可以獲得多少興奮值.1<N<=100000ExampleII-SolutionF[i][k1][k2][p1][p2]表示，前i波食物后，第一頭XXX前兩次吃的食物的種類分別為k1,k2；第二頭XXX前兩次吃的食物種類分別為p1,p2，所能獲得的最大興奮值，轉(zhuǎn)移時(shí)只要枚舉喂給哪只XXX就行了。來(lái)源bzoj1806ExampleIII有兩個(gè)字符串A和B?，F(xiàn)在要從字符串A中取出k個(gè)互不重疊的非空子串，然后把這k個(gè)子串按照其在字符串A中出現(xiàn)的順序依次連接起來(lái)得到一個(gè)新的字符串，問(wèn)有多少種方案可以使得這個(gè)新串與字符串B相等？

A的長(zhǎng)度n≤1000，B的長(zhǎng)度m≤200，k≤200。ExampleIII-Solutionf[i][j][h]表示當(dāng)前已經(jīng)匹配了i個(gè)不重疊子串，A匹配到第j個(gè)位置，B匹配到第h個(gè)位置，的方案數(shù)。然后轉(zhuǎn)移：for(inthh=0;hh<j;hh++)if(s[hh]==c[h-1])f[i][j][h]+=f[i-1][hh][h-1];這樣樸素算法的效率是O(nkm^2)。然后因?yàn)槭呛?，所以我們可以求一個(gè)前綴和，然后轉(zhuǎn)移的效率就會(huì)優(yōu)化到O(nkm)。因?yàn)閮?nèi)存限制，這題還要用滾動(dòng)數(shù)組壓掉k的一維。來(lái)源NOIP2015D2T2(所以NOIP題目不難對(duì)吧)ExampleIV有一個(gè)n*m的方格圖，每個(gè)方格有一定量的錢，現(xiàn)在QWQ從左上角出發(fā)，只能往右或往下走，目的地是右下角。QAQ從右上角出發(fā)，只能往左或往下走，目的地是左下角。他們都很厲害，每經(jīng)過(guò)一個(gè)格子會(huì)把這個(gè)格子的錢給撿走，由于QWQ和QAQ都是追求完美的人，所以他們要求只有一個(gè)格子被他們兩人都經(jīng)過(guò)，現(xiàn)在求他們兩個(gè)人最多能撿到多少錢。注意如果一個(gè)格子被兩個(gè)人同時(shí)經(jīng)過(guò)的話錢只能撿一次。n,m<=1000ExampleIV-Solution我們可以枚舉交點(diǎn)，然后我們可以發(fā)現(xiàn)，QWQ的路徑被分成了兩段，一段是從左上角到交點(diǎn)上面或者左邊，一段是從交點(diǎn)下面或者右邊到右下角。QAQ的路徑也同理。于是我們DP出，從四個(gè)角落出發(fā)到某些點(diǎn)能得到的最多的錢，最后枚舉。交點(diǎn)算一下即可。來(lái)源CodeForces#245div.1BExampleV政府決定將石油資源豐(xi)富(shao)的ZJ省的土地拍賣給私人承包商以建立油井。被拍賣的整塊土地為一個(gè)矩形區(qū)域，被劃分為M×N個(gè)小塊。地質(zhì)調(diào)查局有關(guān)于ZJ省土地石油儲(chǔ)量的估測(cè)數(shù)據(jù)。這些數(shù)據(jù)表示為M×N個(gè)非負(fù)整數(shù)，即對(duì)每一小塊土地石油儲(chǔ)量的估計(jì)值。為了避免出現(xiàn)壟斷，政府規(guī)定每一個(gè)承包商只能承包一個(gè)由K×K塊相連的土地構(gòu)成的正方形區(qū)域。233石油聯(lián)合公司由三個(gè)承包商組成，他們想選擇三塊互不相交的K×K的區(qū)域使得總的收益最大。233公司雇傭你來(lái)寫一個(gè)程序，幫助計(jì)算出他們可以承包的區(qū)域的石油儲(chǔ)量之和的最大值。ExampleV輸入第一行包含三個(gè)整數(shù)M,N,K，其中M和N是矩形區(qū)域的行數(shù)和列數(shù)，K是每一個(gè)承包商承包的正方形的大小（邊長(zhǎng)的塊數(shù)）。接下來(lái)M行，每行有N個(gè)非負(fù)整數(shù)表示這一行每一小塊土地的石油儲(chǔ)量的估計(jì)值。輸出只包含一個(gè)整數(shù)，表示233公司可以承包的區(qū)域的石油儲(chǔ)量之和的最大值。所有的輸入數(shù)據(jù),M,N≤1500。每一小塊土地的石油儲(chǔ)量的估計(jì)值是非負(fù)整數(shù)且≤500。ExampleV-Solution先說(shuō)一個(gè)interesting的事，這題BZOJ樣例格式是錯(cuò)的233。只有可能是右邊這六種情況：對(duì)于每種情況，只要處理出