動態(tài)規(guī)劃例題講解山東師大附中魏銘動態(tài)規(guī)劃例題講解山東師大附中1Preview本節(jié)課主要通過幾道例題，總攬NOIp中較常見的動態(tài)規(guī)劃模型，不會過多涉及優(yōu)化內容。萬丈高樓平地起Preview本節(jié)課主要通過幾道例題，總攬NOIp中較常見的2Preview最長上升子序列內存碎片背包問題最長公共子序列石子合并括號序列決斗三取方格數(shù)選課貪吃的九頭龍Preview最長上升子序列括號序列3最長上升子序列給出一個數(shù)列{a1,a2,...,an}，要求你選出盡量多的元素，使這些元素按其相對位置單調遞增。SampleOutput4SampleInput9

5

8

9

2

3

1

7

4

6最長上升子序列給出一個數(shù)列{a1,a2,...,an}，要求4最長上升子序列算法：動態(tài)規(guī)劃令f[i]表示以ai為結尾的最長上升子序列的長度轉移方程：

f[i]=max(f[j],1<=j<i,a[j]<a[i])+1時間復雜度：O(N^2)最長上升子序列算法：動態(tài)規(guī)劃5最長上升子序列換一種狀態(tài)表示方法令f[i]表示長度為i的上升子序列的結尾數(shù)字最小是多少初始f[0]=-inf,f[i]=inf（inf為無窮大，可取值為大于任意ai絕對值的一個數(shù)字）最長上升子序列換一種狀態(tài)表示方法6最長上升子序列F[0]F[1]F[2]F[3]F[4]初始-infinfinfinfinf插入a1后-inf5infinfinf插入a2后-inf58infinf插入a3后-inf589inf插入a4后-inf289inf插入a5后-inf239inf插入a6后-inf139inf插入a7后-inf137inf插入a8后-inf134inf插入a9后-inf1346SampleInput5

8

9

2

3

1

7

4

6最長上升子序列F[0]F[1]F[2]F[3]F[4]初始-7最長上升子序列f[]是單調遞增的，因為如果有i<j且f[i]>=f[j]，那么f[i]必定可以被f[j]的方案所更新。每處理到一個ai，我們要找到一個k滿足

f[k–1]<ai且f[k]>=ai，并用ai更新f[k]，最終max(k|f[k]!=inf)就是答案?？梢酝ㄟ^二分查找將時間復雜度降至

O(NlogN)最長上升子序列f[]是單調遞增的，因為如果有i<j且f[i]8選人將所有人按照智商排序，以情商為關鍵字，求最長上升子序列的長度即可。選人將所有人按照智商排序，以情商為關鍵字，求最長上升子序列的9內存碎片N個內存申請請求，申請長度為L[i]的內存塊c[i]次。當程序申請長度為L的內存時，也可以給它分配一塊長度為L’（L’>L）的更大的內存塊。內存長度種類不超過K。求最少需要的內存。內存碎片N個內存申請請求，申請長度為L[i]的內存塊c[i]10內存碎片SampleInput32

101

111

2013個內存申請最多2種長度SampleOutput42

方案：

兩個11，一個20內存碎片SampleInputSampleOutput11內存碎片算法：動態(tài)規(guī)劃先將所有L[i]排序。11234467822244

66

881133

666882

33377778這一行是內存申請的長度這三行是內存分配的可能長度內存碎片算法：動態(tài)規(guī)劃這一行是內存申請的長度這三行是內存分配12內存碎片一種內存長度覆蓋的區(qū)間必定是連續(xù)的，并且該內存長度等于覆蓋區(qū)間最后一個內存申請操作的長度。令f[i,j]表示考慮完前i個內存申請操作，并且已經(jīng)使用完j種內存長度的最少需要的內存。內存碎片一種內存長度覆蓋的區(qū)間必定是連續(xù)的，并且該內存長度等13內存碎片f[i,j]=min{

f[k,j-1]+

(c[k+1]+c[k+2]+...+c[i])*L[i],0<=k<i}預處理sc[i]=c[1]+c[2]+...+c[i]f[i,j]=min{

f[k,j-1]+(sc[i]-sc[k])*L[i],0<=k<i)}時間復雜度O(N^2*K)內存碎片f[i,j]=min{

f[k,j-1]+

(c[140/1背包問題共有N件物品，每件物品有一定的重量w[i]和一定的價值v[i]，現(xiàn)在我們有一個最大載重量limit的包，問放入哪些物品能使得總價值最高？w[i]和v[i]均為整數(shù)，N<=100，limit<=100000/1背包問題共有N件物品，每件物品有一定的重量w[i]和一150/1背包問題SampleInput3100

30300

801200

10200共有3件物品

重量分別為30/80/10

價值分別為300/1200/200

背包最大載重量為100SampleOutput14000/1背包問題SampleInputSampleOutput160/1背包問題令f[i,j]表示考慮完前i項物品，并且當前背包承重不大于j的情況下能獲得的最大價值f[i,j]=max(

f[i-1,j],//不選第i項物品

f[i-1,j–w[i]]+v[i])//選擇第i項物品邊界條件f[0,i]=0目標f[n,limit]0/1背包問題令f[i,j]表示考慮完前i項物品，并且當前背170/1背包問題我們注意到，f[i,j]僅與f[i-1,j]和

f[i-1,j-w[i]]有關，因此沒必要保存二維數(shù)組令f[i]表示背包承重不大于i的情況下最大價值0/1背包問題我們注意到，f[i,j]僅與f[i-1,j]和180/1背包問題fillchar(f,sizeof(f),0);

fori:=1tondo

forj:=limitdowntow[i]do

f[j]=max(f[j],f[j-w[i]]+v[i]);

writeln(f[limit]);為什么循環(huán)倒序？0/1背包問題fillchar(f,sizeof(f),0)19完全背包問題共有N種物品，每種物品有一定的重量w[i]和一定的價值v[i]，每種物品有無限個?，F(xiàn)在我們有一個最大載重量limit的包，問放入哪些物品能使得總價值最高？w[i]和v[i]均為整數(shù)，N<=100，limit<=10000完全背包問題共有N種物品，每種物品有一定的重量w[i]和一定20完全背包問題fillchar(f,sizeof(f),0);

fori:=1tondo

forj:=w[i]tolimitdo

f[j]=max(f[j],f[j-w[i]]+v[i]);

writeln(f[limit]);完全背包問題fillchar(f,sizeof(f),0);21多重背包問題共有N種物品，每種物品有一定的重量w[i]和一定的價值v[i]，每種物品有c[i]個?，F(xiàn)在我們有一個最大載重量limit的包，問放入哪些物品能使得總價值最高？w[i]和v[i]均為整數(shù)，N<=100，limit<=10000多重背包問題共有N種物品，每種物品有一定的重量w[i]和一定22多重背包問題SampleInput3100

303002

8012001

102008共有3件物品

重量分別為30/80/10

價值分別為300/1200/200

數(shù)量分別為2/1/8

背包最大載重量為100SampleOutput1700方案：

1件物品1

7件物品3多重背包問題SampleInputSampleOutpu23多重背包問題想法1：把每件物品替換為c[i]件相同的物品，當做0/1背包處理。編號1234567891011W3030801010101010101010V3003001200200200200200200200200200這是原1號物品這是原2號物品這是原3號物品復雜度太高！多重背包問題想法1：把每件物品替換為c[i]件相同的物品，當24多重背包問題想法2：把每件物品按照二進制拆分1=12=1+13=1+24=1+2+15=1+2+26=1+2+37=1+2+48=1+2+4+19=1+2+4+210=1+2+4+3...15=1+2+4+816=1+2+4+8+117=1+2+4+8+2多重背包問題想法2：把每件物品按照二進制拆分25多重背包問題編號1234567W30308010204010V3003001200200400800200這是原1號物品這是原2號物品這是原3號物品多重背包問題編號1234567W3030801020401026最大傷害將AT值看做體積，將造成的傷害看做價值。若先不考慮釋放最后一個魔法的冷卻時間，這就是一個完全背包問題。做完完全背包后，枚舉釋放的最后一次魔法是什么和釋放最后一次魔法時剩余AT是多少，判定是否能夠釋放成功，更新答案。最大傷害將AT值看做體積，將造成的傷害看做價值。27最大傷害樣例1：

驅動魔法所需耗費AT為16，冷卻魔法所耗費AT為5。做完背包后，f[21]=100，f[42]=200，f[63]=300，f[84]=400。枚舉釋放最后一次魔法剩余AT是多少，比如枚舉到AT=84，84+16=100，所以最后一次魔法能夠釋放成功，最大傷害500。最大傷害樣例1：

驅動魔法所需耗費AT為16，冷卻魔法所耗費28最長公共子序列求兩個字符串的最長公共子序列。最長公共子序列定義：

如果存在一個嚴格遞增的下標序列b1,b2,b3,b4....bk,使得所有的Zi

=Xbi

那么Z是X的子序列(注意:子序列和子串不同,子串的下標必須連續(xù),子序列則可以不連續(xù),但要遞增)。給定兩個序列X,Y,如果Z既是X的子序列,也是Y的子序列,那么Z是X和Y的公共子序列。最長公共子序列求兩個字符串的最長公共子序列。29最長公共子序列SampleInputABCDABA

BCABDASampleOutput5最長公共子序列SampleInputSampleOutp30最長公共子序列算法：動態(tài)規(guī)劃f[i,j]表示第一個串的1~i與第二個串的1~j的最長公共子序列長度。f[i,j]=max{

f[i-1,j],

f[i,j-1],

f[i-1,j-1]+1(當Xi=Yj時)}最長公共子序列算法：動態(tài)規(guī)劃31語音識別先去掉所有空格。用f[i,j]表示第一個串匹配到i，第二個串匹配到j的最小差異。f[i,j]=min{

f[i-1,j-1]+abs(s1[i]-s2[j]),

f[i-1,j]+5,

f[i,j-1]+5}語音識別先去掉所有空格。32石子合并N堆石子在操場上排成環(huán)狀，每次可以合并相鄰的兩堆石子，耗費的體力值為兩堆石子數(shù)量和，若想將所有石子合并到一堆，至少耗費多少體力？石子合并N堆石子在操場上排成環(huán)狀，每次可以合并相鄰的兩堆石子33石子合并SampleInput4

4459SampleOutput43石子合并SampleInputSampleOutput34石子合并令f[i,j]表示合并完區(qū)間[i..j]耗費的最小體力f[i,j]=min{f[i,k]+f[k+1,j],i<=k<j}

+w[i,j]環(huán)的處理方法：可以將序列復制一份放到序列后，以樣例為例，新序列為44594459，答案為f[1,4],f[2,5],f[3,6],f[4,7]中的最小值復雜度O(N^3)石子合并令f[i,j]表示合并完區(qū)間[i..j]耗費的最小體35石子合并四邊形不等式在動態(tài)規(guī)劃中，有一類常見的狀態(tài)轉移方程對于i<=i'<=j<=j'假如有w(i,j)+w(i',j')<=w(i',j)+w(i,j')，那么我們稱函數(shù)w滿足四邊形不等式。石子合并四邊形不等式36石子合并定理1：若w滿足四邊形不等式，則m也滿足四邊形不等式，即m(i,j)+m(i',j')<=m(i',j)+m(i,j')令s[i,j]表示f[i,j]取得最優(yōu)值的決策定理2：若f滿足四邊形不等式，則s單調，即s[i,j-1]<=s[i,j]<=s[i+1,j]證明較復雜，略于是復雜度成功降到了O(N^2)石子合并定理1：若w滿足四邊形不等式，則m也滿足四邊形不等式37括號序列空序列是規(guī)則序列。如果S是規(guī)則序列，那么(S)和[S]也是規(guī)則序列。如果A和B都是規(guī)則序列，那么AB也是規(guī)則序列?，F(xiàn)在給出一些由()[]構成的序列，請?zhí)砑颖M量少的括號，得到一個規(guī)則序列。括號序列空序列是規(guī)則序列。38括號序列SampleInput([(]SampleOutput()[()]括號序列SampleInputSampleOutput39括號序列情況1：S形如(S’)或[S’]

只需將S’變成規(guī)則序列即可S=([])S’=[]括號序列情況1：S形如(S’)或[S’]

只需將S’變成規(guī)則40括號序列情況2：S形如(S’或[S’

只需將S’變成規(guī)則序列后，添加)或]即可。S=([]S’=[]括號序列情況2：S形如(S’或[S’

只需將S’變成規(guī)則序列41括號序列情況3：S形如S’)或S’]

只需將S’變成規(guī)則序列后，添加(或(即可。S=()]S’=()括號序列情況3：S形如S’)或S’]

只需將S’變成規(guī)則序列42括號序列情況4：S可被拆分成兩部分S1和S2，只需將S1和S2分別變成規(guī)則序列即可。S=()[]S1=()S2=[]括號序列情況4：S可被拆分成兩部分S1和S2，只需將S1和S43括號序列f[i,j]表示將i..j變成規(guī)則序列至少要添加的括號數(shù)。f[i,j]=min{

f[i+1,j+1],//要求s[i]s[j]為()或[]

f[i+1,j]+1,//要求s[i]為(或[

f[i,j-1]+1,//要求s[j]為)或]

f[i,k]+f[k+1,j],i<=k<j}時間復雜度O(N^3)括號序列f[i,j]表示將i..j變成規(guī)則序列至少要添加的括44決斗N個人排成一圈，他們要決斗N-1場，其中相鄰的兩人決斗（即第i個人與第i+1個人決斗，第N個人與第1個人決斗），死者退出，最終剩下的人勝利。將任意兩個人之間決斗的輸贏情況告訴你，決斗順序由你安排，問哪些人可能成為最終的勝利者？決斗N個人排成一圈，他們要決斗N-1場，其中相鄰的兩人決斗（45決斗SampleInput3

010

001

1001勝2

2勝3

3勝1SampleOutput123若23先決斗，則1勝

若13先決斗，則2勝

若12先決斗，則3勝決斗SampleInputSampleOutput46決斗把環(huán)復制一份，接到環(huán)后面，這樣編號為x的人能勝出的充要條件是他能與自己

“相遇”。123456

1對應4，2對應5，3對應6

由于2可以勝3，因此2將3淘汰后，2和4會相遇，又因為1可以勝2，因此1將2淘汰后，1和4會相遇，所以1可能贏得這場決斗。決斗把環(huán)復制一份，接到環(huán)后面，這樣編號為x的人能勝出的充要條47決斗設meet[i,j]表示i和j是否能夠相遇。若存在i<k<j滿足meet[i,k]&&meet[k,j]&&(defeat[i,k]||defeat[j,k])，則meet[i,j]=true，否則meet[i,j]=false決斗設meet[i,j]表示i和j是否能夠相遇。48決斗fori:=1ton+n-1domeet[i,i+1]=true;forl:=3ton+ndofori:=1ton+n-l+1dobegin

j:=i+l-1;

fork:=i+1toj-1do

ifmeet[i,k]andmeet[k,j]and

(defeat[i,k]ordefeat[j,k])then

meet[i,j]=true;end;fori:=1tondoifmeet[i,i+n]thenwriteln(i);決斗fori:=1ton+n-1domeet[i,49三取方格數(shù)N*N的方格，每個方格有一定的權值，三個人從左上角向右下角走，只能向下或向右，求最大路徑和，走過多次的方格權值只計算一次。三取方格數(shù)N*N的方格，每個方格有一定的權值，三個人從左上角50三取方格數(shù)SampleInput4

1234

2134

1234

1324SampleOutput39三取方格數(shù)SampleInputSampleOutput51三取方格數(shù)由于走過多次的方格權值只算一次，因此貪心不可取?？紤]一個人的情況

f[r,c]=max{f[r’,c’]}+v[r,c]

其中r’c’可以到達rc由此可以推出三個人的方程f[r1,c1,r2,c2,r3,c3]=

max(f[r1’,c1’,r2’,c2’,r3’,c3’])

+value，這里value視情況而定三取方格數(shù)由于走過多次的方格權值只算一次，因此貪心不可取。52三取方格數(shù)時間復雜度為O(N^6)，太高！走了相同步數(shù)的人，r+c是相同的。因此我們可以按斜線劃分狀態(tài)三取方格數(shù)時間復雜度為O(N^6)，太高！53三取方格數(shù)f[s,r1,r2,r3]表示，三個人的x坐標與y坐標和為s，并且縱坐標分別為r1，r2，r3時，最大的路徑權值和。f[s,r1,r2,r3]=

max{f[s-1,r1’,r2’,r3’]}+value

其中f[s-1,r1’,r2’,r3’]可以通過一步到達f[s,r1,r2,r3]，value視情況而定時間復雜度O(N^4)三取方格數(shù)f[s,r1,r2,r3]表示，三個人的x坐標與y54選課有N門選修課，每門課程有一門直接的先修課，課程1沒有先修課。每