ACM程序設(shè)計(jì)謝勇ericxiesina2022/12/191ACM程序設(shè)計(jì)謝勇2022/12/171今天，你AC嗎？依然沒有2022/12/192今天，你AC嗎？依然沒有2022/12/172第四講動(dòng)態(tài)規(guī)劃入門（Dynamicprogramming）2022/12/193第四講動(dòng)態(tài)規(guī)劃入門2022/12/173一、經(jīng)典問題：數(shù)塔問題

有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。2022/12/194一、經(jīng)典問題：數(shù)塔問題 有形如下圖所示的用暴力的方法，可以嗎？2022/12/195用暴力的方法，可以嗎？2022/12/175 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目（2^30=1024^3>10^9=10億）。試想一下：2022/12/196 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如

拒絕暴力，倡導(dǎo)和諧～2022/12/197拒絕暴力，倡導(dǎo)和諧～2022/12/177

從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來(lái)了才能作出決策。 同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。 如數(shù)字2，只要選擇它下面較大值的結(jié)點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最大值。

結(jié)論：自頂向下的分析，自底向上的計(jì)算。考慮一下：2022/12/198 從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最二、經(jīng)典問題：最長(zhǎng)有序子序列I012345678Num[I]1472583692022/12/199二、經(jīng)典問題：最長(zhǎng)有序子序列I012345678Num[I]解決方案：I012345678Num[I]147258369F[I]1232343452022/12/1910解決方案：I012345678Num[I]147258369思考

1160FatMouse'sSpeed

SampleInput

60081300600021005002000100040001100300060002000800014006000120020001900SampleOutput

445972022/12/1911思考1160FatMouse'sSpeedSam再思考（1087）SuperJumping!Jumping! Juping!

2022/12/1912再思考（1087）SuperJumping!Jumpi解題思路？2022/12/1913解題思路？2022/12/1713三、經(jīng)典問題：最長(zhǎng)公共子序列HDOJ-1159：SampleInput

abcfbcabfcab

programmingcontest

abcdmnpSampleOutput

4

2

02022/12/1914三、經(jīng)典問題：最長(zhǎng)公共子序列HDOJ-1159：Sampleabcfbca111111b122222f122333c123334a123334b123344輔助空間變化示意圖2022/12/1915abcfbca111111b122222f122333c12f(i,j)=

{由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有關(guān),而在計(jì)算f(i,j)時(shí),只要選擇一個(gè)合適的順序,就可以保證這三項(xiàng)都已經(jīng)計(jì)算出來(lái)了,這樣就可以計(jì)算出f(i,j).這樣一直推到f(len(a),len(b))就得到所要求的解了.f(i-1,j-1)+1(a[i]==b[j])max(f(i-1,j),f(i,j-1))(a[i]!=b[j])

子結(jié)構(gòu)特征：2022/12/1916f(i,j)={f(i-1,j-1)+1(a[i]==b四、經(jīng)典問題：1421

搬寢室

SampleInput

21

13

SampleOutput

42022/12/1917四、經(jīng)典問題：1421搬寢室 SampleInput2搬寢室是很累的,xhd深有體會(huì).時(shí)間追述2019年7月9號(hào),那天xhd迫于無(wú)奈要從27號(hào)樓搬到3號(hào)樓,因?yàn)?0號(hào)要封樓了.看著寢室里的n件物品,xhd開始發(fā)呆,因?yàn)閚是一個(gè)小于2000的整數(shù),實(shí)在是太多了,于是xhd決定隨便搬2*k件過(guò)去就行了.但還是會(huì)很累,因?yàn)?*k也不小是一個(gè)不大于n的整數(shù).幸運(yùn)的是xhd根據(jù)多年的搬東西的經(jīng)驗(yàn)發(fā)現(xiàn)每搬一次的疲勞度是和左右手的物品的重量差的平方成正比(這里補(bǔ)充一句,xhd每次搬兩件東西,左手一件右手一件).例如xhd左手拿重量為3的物品,右手拿重量為6的物品,則他搬完這次的疲勞度為(6-3)^2=9.現(xiàn)在可憐的xhd希望知道搬完這2*k件物品后的最佳狀態(tài)是怎樣的(也就是最低的疲勞度),請(qǐng)告訴他吧.2022/12/1918搬寢室是很累的,xhd深有體會(huì).時(shí)間追述2019年7月9號(hào),第一感覺：根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？證明：假設(shè)四個(gè)從小到大的數(shù)：a、b、c、d，只需證明以下表達(dá)式成立即可：(a-b)^2+(c-d)^2<(a-c)^2+(b-d)^2(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2……(略)2022/12/1919第一感覺：根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是預(yù)備工作：排序！2022/12/1920預(yù)備工作：排序！2022/12/1720第二感覺：對(duì)于一次操作，顯然提的物品重量越接近越好，是不是可以貪心呢？請(qǐng)思考…考慮以下情況：

14581011什么結(jié)論？2022/12/1921第二感覺：對(duì)于一次操作，顯然提的物品重量越接近越好，是不是可詳細(xì)分析：從最簡(jiǎn)單的情況考慮：2個(gè)物品選一對(duì)，結(jié)論顯然結(jié)論？4個(gè)物品選一對(duì)？（如何利用前面的知識(shí)）3個(gè)物品選一對(duì)，…n個(gè)物品選一對(duì)，…最終問題：n個(gè)物品選k對(duì)，如何？（n>=2k）n個(gè)物品選二對(duì)，…2022/12/1922詳細(xì)分析：從最簡(jiǎn)單的情況考慮：結(jié)論？4個(gè)物品選一對(duì)？（如何利f(i,j)表示前j個(gè)取i對(duì)最小的疲勞度f(wàn)(i,j)=min(f(i,j-1),f(i-1,j-2)+(item(j)-item(j-1))^2)2022/12/1923f(i,j)表示前j個(gè)取i對(duì)最小的疲勞度2022/12/1五、經(jīng)典問題：1058HumbleNumbers

ProblemDescriptionAnumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers.

Writeaprogramtofindandprintthenthelementinthissequence2022/12/1924五、經(jīng)典問題：1058HumbleNumbers Pr算法分析：典型的DP!1->?1->2=min(1*2,1*3,1*5,1*7)1->2->3=min(2*2,1*3,1*5,1*7)1->2->3->4=min(2*2,2*3,1*5,1*7)1->2->3->4->5=min(3*2,2*3,1*5,1*7)2022/12/1925算法分析：典型的DP!1->?1->2=min(1*2,狀態(tài)轉(zhuǎn)移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7) (n>i,j,k,m)特別的：

i,j,k,m只有在本項(xiàng)被選中后才移動(dòng)2022/12/1926狀態(tài)轉(zhuǎn)移方程？F(n)=min(F(i)*2,F(j)*3,關(guān)鍵問題：這個(gè)題目的哪些經(jīng)驗(yàn)值得我們借鑒？2022/12/1927關(guān)鍵問題：這個(gè)題目的哪些經(jīng)驗(yàn)值得我們借鑒？2022/12/1思考：免費(fèi)餡餅

2022/12/1928思考：免費(fèi)餡餅2022/12/1728如何解決？請(qǐng)發(fā)表見解2022/12/1929如何解決？請(qǐng)發(fā)表見解2022/12/1729

如果各個(gè)子問題不是獨(dú)立的，不同的子問題的個(gè)數(shù)只是多項(xiàng)式量級(jí)，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時(shí)候再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算。

由此而來(lái)的基本思路是——用一個(gè)表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。小結(jié)：DP的基本思想

2022/12/1930 如果各個(gè)子問題不是獨(dú)立的，不同的子問題的個(gè)數(shù)只是多項(xiàng)式量課后任務(wù)：

《ACM程序設(shè)計(jì)》作業(yè)（4）ACM程序設(shè)計(jì)作業(yè)1-3請(qǐng)補(bǔ)交2022/12/1931課后任務(wù)：2022/12/1731 該加油了~2022/12/1932 該加油了~2022/12/1732ACM程序設(shè)計(jì)謝勇ericxiesina2022/12/1933ACM程序設(shè)計(jì)謝勇2022/12/171今天，你AC嗎？依然沒有2022/12/1934今天，你AC嗎？依然沒有2022/12/172第四講動(dòng)態(tài)規(guī)劃入門（Dynamicprogramming）2022/12/1935第四講動(dòng)態(tài)規(guī)劃入門2022/12/173一、經(jīng)典問題：數(shù)塔問題

有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。2022/12/1936一、經(jīng)典問題：數(shù)塔問題 有形如下圖所示的用暴力的方法，可以嗎？2022/12/1937用暴力的方法，可以嗎？2022/12/175 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目（2^30=1024^3>10^9=10億）。試想一下：2022/12/1938 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如

拒絕暴力，倡導(dǎo)和諧～2022/12/1939拒絕暴力，倡導(dǎo)和諧～2022/12/177

從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來(lái)了才能作出決策。 同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。 如數(shù)字2，只要選擇它下面較大值的結(jié)點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最大值。

結(jié)論：自頂向下的分析，自底向上的計(jì)算。考慮一下：2022/12/1940 從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最二、經(jīng)典問題：最長(zhǎng)有序子序列I012345678Num[I]1472583692022/12/1941二、經(jīng)典問題：最長(zhǎng)有序子序列I012345678Num[I]解決方案：I012345678Num[I]147258369F[I]1232343452022/12/1942解決方案：I012345678Num[I]147258369思考

1160FatMouse'sSpeed

SampleInput

60081300600021005002000100040001100300060002000800014006000120020001900SampleOutput

445972022/12/1943思考1160FatMouse'sSpeedSam再思考（1087）SuperJumping!Jumping! Juping!

2022/12/1944再思考（1087）SuperJumping!Jumpi解題思路？2022/12/1945解題思路？2022/12/1713三、經(jīng)典問題：最長(zhǎng)公共子序列HDOJ-1159：SampleInput

abcfbcabfcab

programmingcontest

abcdmnpSampleOutput

4

2

02022/12/1946三、經(jīng)典問題：最長(zhǎng)公共子序列HDOJ-1159：Sampleabcfbca111111b122222f122333c123334a123334b123344輔助空間變化示意圖2022/12/1947abcfbca111111b122222f122333c12f(i,j)=

{由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有關(guān),而在計(jì)算f(i,j)時(shí),只要選擇一個(gè)合適的順序,就可以保證這三項(xiàng)都已經(jīng)計(jì)算出來(lái)了,這樣就可以計(jì)算出f(i,j).這樣一直推到f(len(a),len(b))就得到所要求的解了.f(i-1,j-1)+1(a[i]==b[j])max(f(i-1,j),f(i,j-1))(a[i]!=b[j])

子結(jié)構(gòu)特征：2022/12/1948f(i,j)={f(i-1,j-1)+1(a[i]==b四、經(jīng)典問題：1421

搬寢室

SampleInput

21

13

SampleOutput

42022/12/1949四、經(jīng)典問題：1421搬寢室 SampleInput2搬寢室是很累的,xhd深有體會(huì).時(shí)間追述2019年7月9號(hào),那天xhd迫于無(wú)奈要從27號(hào)樓搬到3號(hào)樓,因?yàn)?0號(hào)要封樓了.看著寢室里的n件物品,xhd開始發(fā)呆,因?yàn)閚是一個(gè)小于2000的整數(shù),實(shí)在是太多了,于是xhd決定隨便搬2*k件過(guò)去就行了.但還是會(huì)很累,因?yàn)?*k也不小是一個(gè)不大于n的整數(shù).幸運(yùn)的是xhd根據(jù)多年的搬東西的經(jīng)驗(yàn)發(fā)現(xiàn)每搬一次的疲勞度是和左右手的物品的重量差的平方成正比(這里補(bǔ)充一句,xhd每次搬兩件東西,左手一件右手一件).例如xhd左手拿重量為3的物品,右手拿重量為6的物品,則他搬完這次的疲勞度為(6-3)^2=9.現(xiàn)在可憐的xhd希望知道搬完這2*k件物品后的最佳狀態(tài)是怎樣的(也就是最低的疲勞度),請(qǐng)告訴他吧.2022/12/1950搬寢室是很累的,xhd深有體會(huì).時(shí)間追述2019年7月9號(hào),第一感覺：根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？證明：假設(shè)四個(gè)從小到大的數(shù)：a、b、c、d，只需證明以下表達(dá)式成立即可：(a-b)^2+(c-d)^2<(a-c)^2+(b-d)^2(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2……(略)2022/12/1951第一感覺：根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是預(yù)備工作：排序！2022/12/1952預(yù)備工作：排序！2022/12/1720第二感覺：對(duì)于一次操作，顯然提的物品重量越接近越好，是不是可以貪心呢？請(qǐng)思考…考慮以下情況：

14581011什么結(jié)論？2022/12/1953第二感覺：對(duì)于一次操作，顯然提的物品重量越接近越好，是不是可詳細(xì)分析：從最簡(jiǎn)單的情況考慮：2個(gè)物品選一對(duì)，結(jié)論顯然結(jié)論？4個(gè)物品選一對(duì)？（如何利用前面的知識(shí)）3個(gè)物品選一對(duì)，…n個(gè)物品選一對(duì)，…最終問題：n個(gè)物品選k對(duì)，如何？（n>=2k）n個(gè)物品選二對(duì)，…2022/12/1954詳細(xì)分析：從最簡(jiǎn)單的情況考慮：結(jié)論？4個(gè)物品選一對(duì)？（如何利f(i,j)表示前j個(gè)取i對(duì)最小的疲勞度f(wàn)(i,j)=min(f(i,j-1),f(i-1,j-2)+(item(j)-item(j-1))^2)2022/12/1955f(i,j)表示前j個(gè)取i對(duì)最小的疲勞度2022/12/1五、經(jīng)典問題：1058HumbleNumbers

ProblemDescriptionAnumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers.

Writeaprogramtofindandprintthenthelementinthiss