最新-C案例04動(dòng)態(tài)規(guī)劃-課件

第四講動(dòng)態(tài)規(guī)劃（Dynamicprogramming）2022/12/211第四講動(dòng)態(tài)規(guī)劃2022/12/171一、經(jīng)典問(wèn)題：數(shù)塔問(wèn)題

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

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

從頂點(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/216 從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最

思路：從倒數(shù)第二行起，按照狀態(tài)轉(zhuǎn)移方程dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+val[i][j]向上遞推，直到val[1][1]，此時(shí)dp[1][1]就是結(jié)果2022/12/217 思路：從倒數(shù)第二行起，按照狀態(tài)轉(zhuǎn)移方程2022/12/1二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列[問(wèn)題描述]

找出由n個(gè)元素組成的序列的最長(zhǎng)有序子序列長(zhǎng)度及其中一個(gè)最長(zhǎng)有序子序列

（注：這里有序指非遞減順序，且不要求子序列連續(xù)）。

例如，對(duì)于序列[3,7,1,5,9,3]，其中最長(zhǎng)有序子序列長(zhǎng)度為3，這樣的子序列有：

[3,7,9]、[1,5,9]、[3,5,9]。2022/12/218二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列[問(wèn)題描述]

找出由n個(gè)二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列

2022/12/219二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列

2022/12/179二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/2110二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/1710二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/2111二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/1711三

1160FatMouse'sSpeed

ProblemDescriptionFatMousebelievesthatthefatteramouseis,thefasteritruns.Todisprovethis,youwanttotakethedataonacollectionofmiceandputaslargeasubsetofthisdataaspossibleintoasequencesothattheweightsareincreasing,butthespeedsaredecreasing.

InputInputcontainsdataforabunchofmice,onemouseperline,terminatedbyendoffile.

Thedataforaparticularmousewillconsistofapairofintegers:thefirstrepresentingitssizeingramsandthesecondrepresentingitsspeedincentimeterspersecond.Bothintegersarebetween1and10000.Thedataineachtestcasewillcontaininformationforatmost1000mice.

Twomicemayhavethesameweight,thesamespeed,oreventhesameweightandspeed.

2022/12/2112三1160FatMouse'sSpeedPro三

1160FatMouse'sSpeed

OutputYourprogramshouldoutputasequenceoflinesofdata;thefirstlineshouldcontainanumbern;theremainingnlinesshouldeachcontainasinglepositiveinteger(eachonerepresentingamouse).Ifthesenintegersarem[1],m[2],...,m[n]thenitmustbethecasethat

W[m[1]]<W[m[2]]<...<W[m[n]]

and

S[m[1]]>S[m[2]]>...>S[m[n]]

Inorderfortheanswertobecorrect,nshouldbeaslargeaspossible.

Allinequalitiesarestrict:weightsmustbestrictlyincreasing,andspeedsmustbestrictlydecreasing.Theremaybemanycorrectoutputsforagiveninput,yourprogramonlyneedstofindone.

2022/12/2113三1160FatMouse'sSpeedOutp三1160FatMouse'sSpeed

SampleInput

60081300600021005002000100040001100300060002000800014006000120020001900SampleOutput

445972022/12/2114三1160FatMouse'sSpeedSamp三

1160FatMouse'sSpeed

解題思路：題目要求找到的體重遞增，速度遞減老鼠，先把老鼠的體重進(jìn)行升序排序然后算出速度的最長(zhǎng)遞減子序列。

2022/12/2115三1160FatMouse'sSpeed解題思路四1087SuperJumping!Jumping! Juping!

ProblemDescriptionNowadays,akindofchessgamecalled“SuperJumping!Jumping!Jumping!”isverypopularinHDU.Maybeyouareagoodboy,andknowlittleaboutthisgame,soIintroduceittoyounow.

Thegamecanbeplayedbytwoormorethantwoplayers.Itconsistsofachessboard（棋盤）andsomechessmen（棋子）,andallchessmenaremarkedbyapositiveintegeror“start”or“end”.Theplayerstartsfromstart-pointandmustjumpsintoend-pointfinally.Inthecourseofjumping,theplayerwillvisitthechessmeninthepath,buteveryonemustjumpsfromonechessmantoanotherabsolutelybigger(youcanassumestart-pointisaminimumandend-pointisamaximum.).Andallplayerscannotgobackwards.Onejumpingcangofromachessmantonext,alsocangoacrossmanychessmen,andevenyoucanstraightlygettoend-pointfromstart-point.Ofcourseyougetzeropointinthissituation.Aplayerisawinnerifandonlyifhecangetabiggerscoreaccordingtohisjumpingsolution.Notethatyourscorecomesfromthesumofvalueonthechessmeninyoujumpingpath.

Yourtaskistooutputthemaximumvalueaccordingtothegivenchessmenlist.2022/12/2116四1087SuperJumping!Jumping四1087SuperJumping!Jumping! Juping!InputInputcontainsmultipletestcases.Eachtestcaseisdescribedinalineasfollow:

Nvalue_1value_2…value_N

ItisguarantiedthatNisnotmorethan1000andallvalue_iareintherangeof32-int.

Atestcasestartingwith0terminatestheinputandthistestcaseisnottobeprocessed.

OutputForeachcase,printthemaximumaccordingtorules,andonelineonecase.2022/12/2117四1087SuperJumping!Jumping四1087SuperJumping!Jumping! Juping!SampleInput313241234433210

SampleOutput41032022/12/2118四1087SuperJumping!Jumping解題思路？找序列中最大升序子序列的和

2022/12/2119解題思路？找序列中最大升序子序列的和2022/12/171動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022/12/2120動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2022/12/2121但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)2022/12/2122如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2022/12/2123動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。2022動(dòng)態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結(jié)構(gòu)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。同一個(gè)問(wèn)題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問(wèn)題的維度低）2022/12/2124動(dòng)態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結(jié)構(gòu)問(wèn)題的最優(yōu)解包含著其子動(dòng)態(tài)規(guī)劃算法的基本要素二、重疊子問(wèn)題遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。2022/12/2125動(dòng)態(tài)規(guī)劃算法的基本要素二、重疊子問(wèn)題遞歸算法求解問(wèn)題時(shí)，每次動(dòng)態(tài)規(guī)劃算法的基本要素三、備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題的重復(fù)求解。intLookupChain(inti，intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i，i)+LookupChain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}2022/12/2126動(dòng)態(tài)規(guī)劃算法的基本要素三、備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列ProblemDescriptionAsubsequenceofagivensequenceisthegivensequencewithsomeelements(possiblenone)leftout.GivenasequenceX=<x1,x2,...,xm>anothersequenceZ=<z1,z2,...,zk>isasubsequenceofXifthereexistsastrictlyincreasingsequence<i1,i2,...,ik>ofindicesofXsuchthatforallj=1,2,...,k,xij=zj.Forexample,Z=<a,b,f,c>isasubsequenceofX=<a,b,c,f,b,c>withindexsequence<1,2,4,6>.GiventwosequencesXandYtheproblemistofindthelengthofthemaximum-lengthcommonsubsequenceofXandY.

Theprograminputisfromatextfile.Eachdatasetinthefilecontainstwostringsrepresentingthegivensequences.Thesequencesareseparatedbyanynumberofwhitespaces.Theinputdataarecorrect.Foreachsetofdatatheprogramprintsonthestandardoutputthelengthofthemaximum-lengthcommonsubsequencefromthebeginningofaseparateline.

2022/12/2127五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列ProblemDescript五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列HDOJ-1159：SampleInput

abcfbcabfcab

programmingcontest

abcdmnpSampleOutput

4

2

02022/12/2128五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列HDOJ-1159：Sample最長(zhǎng)公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長(zhǎng)公共子序列。

2022/12/2129最長(zhǎng)公共子序列若給定序列X={x1,x2,…,xm}，則另一最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。(2)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長(zhǎng)公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長(zhǎng)公共子序列。由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2022/12/2130最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y=子問(wèn)題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：2022/12/2131子問(wèn)題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)abcfbca111111b122222f122333c123334a123334b123344輔助空間變化示意圖2022/12/2132abcfbca111111b122222f122333c12計(jì)算最優(yōu)值由于在所考慮的子問(wèn)題空間中，總共有θ(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}構(gòu)造最長(zhǎng)公共子序列voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}2022/12/2133計(jì)算最優(yōu)值由于在所考慮的子問(wèn)題空間中，總共有θ(mn)個(gè)不同算法的改進(jìn)在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個(gè)值所確定的。如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。2022/12/2134算法的改進(jìn)在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組六、經(jīng)典問(wèn)題：1421

搬寢室

ProblemDescription

搬寢室是很累的,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/2135六、經(jīng)典問(wèn)題：1421搬寢室 ProblemDescr六、經(jīng)典問(wèn)題：1421

搬寢室

Input每組輸入數(shù)據(jù)有兩行,第一行有兩個(gè)數(shù)n,k(2<=2*k<=n<2000).第二行有n個(gè)整數(shù)分別表示n件物品的重量(重量是一個(gè)小于2^15的正整數(shù)).

Output對(duì)應(yīng)每組輸入數(shù)據(jù),輸出數(shù)據(jù)只有一個(gè)表示他的最少的疲勞度,每個(gè)一行.2022/12/2136六、經(jīng)典問(wèn)題：1421搬寢室 Input2022/12/六、經(jīng)典問(wèn)題：1421

搬寢室

SampleInput

21

13

SampleOutput

42022/12/2137六、經(jīng)典問(wèn)題：1421搬寢室 SampleInput2第一感覺(jué)：根據(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/2138第一感覺(jué)：根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是預(yù)備工作：排序！2022/12/2139預(yù)備工作：排序！2022/12/1739第二感覺(jué)：對(duì)于一次操作，顯然提的物品重量越接近越好，是不是可以貪心呢？請(qǐng)思考…考慮以下情況：

1458什么結(jié)論？2022/12/2140第二感覺(jué)：對(duì)于一次操作，顯然提的物品重量越接近越好，是不是可詳細(xì)分析：從最簡(jiǎn)單的情況考慮：2個(gè)物品選一對(duì)，結(jié)論顯然結(jié)論？4個(gè)物品選一對(duì)？（如何利用前面的知識(shí)）3個(gè)物品選一對(duì)，…n個(gè)物品選一對(duì)，…最終問(wèn)題：n個(gè)物品選k對(duì)（n>=2k），如何？n個(gè)物品選二對(duì)，…2022/12/2141詳細(xì)分析：從最簡(jiǎn)單的情況考慮：結(jié)論？4個(gè)物品選一對(duì)？（如何利解題思路先對(duì)物品的重量進(jìn)行排序，取相鄰的物品，將相鄰的物品的差的平方另外存儲(chǔ)，得到狀態(tài)轉(zhuǎn)移方程：dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]),s[i]是代表i,i+1這兩個(gè)物品的疲憊度.因?yàn)閟[i-1],s[i].代表的是ai-1,ai,ai+1的疲憊度，中間共享了一個(gè)ai，所以第二項(xiàng)要用dp[i-2].2022/12/2142解題思路先對(duì)物品的重量進(jìn)行排序，取相鄰的物品，將相鄰的物品的參考代碼#include<iostream>

#include<algorithm>

using

namespace

std;

#define

INF

0x7fffffff

int

dp[2000][2000],a[2000],s[2000];

int

main()

{

int

n,k,i,j;

while(

scanf("%d%d",&n,&k)!=EOF){

for(

i=1;

i<=n;

i++)

scanf("%d",&a[i]);

sort(a,a+n+1);

for(

i=1;

i<=n;

i++)

for(

j=1;

j<=n/2;

j++)

dp[i][j]=INF;

for(

i=2;

i<=n;

i++)

s[i]=(a[i]-a[i-1])*(a[i]-a[i-1]);

for(

i=2;

i<=n;

i++)

for(

j=1;

j<=i/2;

j++)

dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]);

printf("%d\n",dp[n][k]);

}

return

0;

}

2022/12/2143參考代碼#include<iostream>

2022/1七、經(jīng)典問(wèn)題：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/2144七、經(jīng)典問(wèn)題：1058HumbleNumbers Pr七、經(jīng)典問(wèn)題：1058HumbleNumbers

InputTheinputconsistsofoneormoretestcases.Eachtestcaseconsistsofoneintegernwith1<=n<=5842.Inputisterminatedbyavalueofzero(0)forn.

OutputForeachtestcase,printonelinesaying"Thenthhumblenumberisnumber.".Dependingonthevalueofn,thecorrectsuffix"st","nd","rd",or"th"fortheordinalnumbernthhastobeusedlikeitisshowninthesampleoutput.2022/12/2145七、經(jīng)典問(wèn)題：1058HumbleNumbers In七、經(jīng)典問(wèn)題：1058HumbleNumbers

2022/12/2146七、經(jīng)典問(wèn)題：1058HumbleNumbers 20算法分析：典型的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/2147算法分析：典型的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/2148狀態(tài)轉(zhuǎn)移方程？F(n)=min(F(i)*2,F(j)*3,關(guān)鍵問(wèn)題：這個(gè)題目的哪些經(jīng)驗(yàn)值得我們借鑒？2022/12/2149關(guān)鍵問(wèn)題：這個(gè)題目的哪些經(jīng)驗(yàn)值得我們借鑒？2022/12/1八免費(fèi)餡餅

11762022/12/2150八免費(fèi)餡餅11762022/12/1750八免費(fèi)餡餅

1176ProblemDescription都說(shuō)天上不會(huì)掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說(shuō)來(lái)gameboy的人品實(shí)在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在了地上當(dāng)然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè)都不能站人，所以他只能在小徑上接。由于gameboy平時(shí)老呆在房間里玩游戲，雖然在游戲中是個(gè)身手敏捷的高手，但在現(xiàn)實(shí)中運(yùn)動(dòng)神經(jīng)特別遲鈍，每秒種只有在移動(dòng)不超過(guò)一米的范圍內(nèi)接住墜落的餡餅?，F(xiàn)在給這條小徑如圖標(biāo)上坐標(biāo)：

為了使問(wèn)題簡(jiǎn)化，假設(shè)在接下來(lái)的一段時(shí)間里，餡餅都掉落在0-10這11個(gè)位置。開始時(shí)gameboy站在5這個(gè)位置，因此在第一秒，他只能接到4,5,6這三個(gè)位置中其中一個(gè)位置上的餡餅。問(wèn)gameboy最多可能接到多少個(gè)餡餅？（假設(shè)他的背包可以容納無(wú)窮多個(gè)餡餅）2022/12/2151八免費(fèi)餡餅1176ProblemDescription八免費(fèi)餡餅

1176Input輸入數(shù)據(jù)有多組。每組數(shù)據(jù)的第一行為以正整數(shù)n(0<n<100000)，表示有n個(gè)餡餅掉在這條小徑上。在結(jié)下來(lái)的n行中，每行有兩個(gè)整數(shù)x,T(0<T<100000),表示在第T秒有一個(gè)餡餅掉在x點(diǎn)上。同一秒鐘在同一點(diǎn)上可能掉下多個(gè)餡餅。n=0時(shí)輸入結(jié)束。

Output每一組輸入數(shù)據(jù)對(duì)應(yīng)一行輸出。輸出一個(gè)整數(shù)m，表示gameboy最多可能接到m個(gè)餡餅。

提示：本題的輸入數(shù)據(jù)量比較大，建議用scanf讀入，用cin可能會(huì)超時(shí)。2022/12/2152八免費(fèi)餡餅1176Input2022/12/1752八免費(fèi)餡餅

1176SampleInput65141617272830

SampleOutput42022/12/2153八免費(fèi)餡餅1176SampleInput2022/12如何解決？請(qǐng)發(fā)表見(jiàn)解2022/12/2154如何解決？請(qǐng)發(fā)表見(jiàn)解2022/12/1754解題思路有點(diǎn)類似于數(shù)塔Dp[t][i]=MAX(Dp[t-1][i-1],Dp[t-1][i],Dp[t-1][i+1])+DATA[t][i];2022/12/2155解題思路有點(diǎn)類似于數(shù)塔Dp[t][i]=MAX(Dp[t-1自學(xué)題請(qǐng)大家自學(xué)課本P239最短路徑問(wèn)題P247插入乘號(hào)問(wèn)題2022/12/2156自學(xué)題請(qǐng)大家自學(xué)課本2022/12/1756

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

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

2022/12/2157 如果各個(gè)子問(wèn)題不是獨(dú)立的，不同的子問(wèn)題的個(gè)數(shù)只是多項(xiàng)式量第四講動(dòng)態(tài)規(guī)劃（Dynamicprogramming）2022/12/2158第四講動(dòng)態(tài)規(guī)劃2022/12/171一、經(jīng)典問(wèn)題：數(shù)塔問(wèn)題

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

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

從頂點(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/2163 從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最

思路：從倒數(shù)第二行起，按照狀態(tài)轉(zhuǎn)移方程dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+val[i][j]向上遞推，直到val[1][1]，此時(shí)dp[1][1]就是結(jié)果2022/12/2164 思路：從倒數(shù)第二行起，按照狀態(tài)轉(zhuǎn)移方程2022/12/1二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列[問(wèn)題描述]

找出由n個(gè)元素組成的序列的最長(zhǎng)有序子序列長(zhǎng)度及其中一個(gè)最長(zhǎng)有序子序列

（注：這里有序指非遞減順序，且不要求子序列連續(xù)）。

例如，對(duì)于序列[3,7,1,5,9,3]，其中最長(zhǎng)有序子序列長(zhǎng)度為3，這樣的子序列有：

[3,7,9]、[1,5,9]、[3,5,9]。2022/12/2165二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列[問(wèn)題描述]

找出由n個(gè)二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列

2022/12/2166二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列

2022/12/179二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/2167二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/1710二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/2168二、經(jīng)典問(wèn)題：最長(zhǎng)有序子序列2022/12/1711三

1160FatMouse'sSpeed

ProblemDescriptionFatMousebelievesthatthefatteramouseis,thefasteritruns.Todisprovethis,youwanttotakethedataonacollectionofmiceandputaslargeasubsetofthisdataaspossibleintoasequencesothattheweightsareincreasing,butthespeedsaredecreasing.

InputInputcontainsdataforabunchofmice,onemouseperline,terminatedbyendoffile.

Thedataforaparticularmousewillconsistofapairofintegers:thefirstrepresentingitssizeingramsandthesecondrepresentingitsspeedincentimeterspersecond.Bothintegersarebetween1and10000.Thedataineachtestcasewillcontaininformationforatmost1000mice.

Twomicemayhavethesameweight,thesamespeed,oreventhesameweightandspeed.

2022/12/2169三1160FatMouse'sSpeedPro三

1160FatMouse'sSpeed

OutputYourprogramshouldoutputasequenceoflinesofdata;thefirstlineshouldcontainanumbern;theremainingnlinesshouldeachcontainasinglepositiveinteger(eachonerepresentingamouse).Ifthesenintegersarem[1],m[2],...,m[n]thenitmustbethecasethat

W[m[1]]<W[m[2]]<...<W[m[n]]

and

S[m[1]]>S[m[2]]>...>S[m[n]]

Inorderfortheanswertobecorrect,nshouldbeaslargeaspossible.

Allinequalitiesarestrict:weightsmustbestrictlyincreasing,andspeedsmustbestrictlydecreasing.Theremaybemanycorrectoutputsforagiveninput,yourprogramonlyneedstofindone.

2022/12/2170三1160FatMouse'sSpeedOutp三1160FatMouse'sSpeed

SampleInput

60081300600021005002000100040001100300060002000800014006000120020001900SampleOutput

445972022/12/2171三1160FatMouse'sSpeedSamp三

1160FatMouse'sSpeed

解題思路：題目要求找到的體重遞增，速度遞減老鼠，先把老鼠的體重進(jìn)行升序排序然后算出速度的最長(zhǎng)遞減子序列。

2022/12/2172三1160FatMouse'sSpeed解題思路四1087SuperJumping!Jumping! Juping!

ProblemDescriptionNowadays,akindofchessgamecalled“SuperJumping!Jumping!Jumping!”isverypopularinHDU.Maybeyouareagoodboy,andknowlittleaboutthisgame,soIintroduceittoyounow.

Thegamecanbeplayedbytwoormorethantwoplayers.Itconsistsofachessboard（棋盤）andsomechessmen（棋子）,andallchessmenaremarkedbyapositiveintegeror“start”or“end”.Theplayerstartsfromstart-pointandmustjumpsintoend-pointfinally.Inthecourseofjumping,theplayerwillvisitthechessmeninthepath,buteveryonemustjumpsfromonechessmantoanotherabsolutelybigger(youcanassumestart-pointisaminimumandend-pointisamaximum.).Andallplayerscannotgobackwards.Onejumpingcangofromachessmantonext,alsocangoacrossmanychessmen,andevenyoucanstraightlygettoend-pointfromstart-point.Ofcourseyougetzeropointinthissituation.Aplayerisawinnerifandonlyifhecangetabiggerscoreaccordingtohisjumpingsolution.Notethatyourscorecomesfromthesumofvalueonthechessmeninyoujumpingpath.

Yourtaskistooutputthemaximumvalueaccordingtothegivenchessmenlist.2022/12/2173四1087SuperJumping!Jumping四1087SuperJumping!Jumping! Juping!InputInputcontainsmultipletestcases.Eachtestcaseisdescribedinalineasfollow:

Nvalue_1value_2…value_N

ItisguarantiedthatNisnotmorethan1000andallvalue_iareintherangeof32-int.

Atestcasestartingwith0terminatestheinputandthistestcaseisnottobeprocessed.

OutputForeachcase,printthemaximumaccordingtorules,andonelineonecase.2022/12/2174四1087SuperJumping!Jumping四1087SuperJumping!Jumping! Juping!SampleInput313241234433210

SampleOutput41032022/12/2175四1087SuperJumping!Jumping解題思路？找序列中最大升序子序列的和

2022/12/2176解題思路？找序列中最大升序子序列的和2022/12/171動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022/12/2177動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2022/12/2178但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)2022/12/2179如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2022/12/2180動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。2022動(dòng)態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結(jié)構(gòu)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。同一個(gè)問(wèn)題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問(wèn)題的維度低）2022/12/2181動(dòng)態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結(jié)構(gòu)問(wèn)題的最優(yōu)解包含著其子動(dòng)態(tài)規(guī)劃算法的基本要素二、重疊子問(wèn)題遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。2022/12/2182動(dòng)態(tài)規(guī)劃算法的基本要素二、重疊子問(wèn)題遞歸算法求解問(wèn)題時(shí)，每次動(dòng)態(tài)規(guī)劃算法的基本要素三、備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題的重復(fù)求解。intLookupChain(inti，intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i，i)+LookupChain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}2022/12/2183動(dòng)態(tài)規(guī)劃算法的基本要素三、備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列ProblemDescriptionAsubsequenceofagivensequenceisthegivensequencewithsomeelements(possiblenone)leftout.GivenasequenceX=<x1,x2,...,xm>anothersequenceZ=<z1,z2,...,zk>isasubsequenceofXifthereexistsastrictlyincreasingsequence<i1,i2,...,ik>ofindicesofXsuchthatforallj=1,2,...,k,xij=zj.Forexample,Z=<a,b,f,c>isasubsequenceofX=<a,b,c,f,b,c>withindexsequence<1,2,4,6>.GiventwosequencesXandYtheproblemistofindthelengthofthemaximum-lengthcommonsubsequenceofXandY.

Theprograminputisfromatextfile.Eachdatasetinthefilecontainstwostringsrepresentingthegivensequences.Thesequencesareseparatedbyanynumberofwhitespaces.Theinputdataarecorrect.Foreachsetofdatatheprogramprintsonthestandardoutputthelengthofthemaximum-lengthcommonsubsequencefromthebeginningofaseparateline.

2022/12/2184五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列ProblemDescript五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列HDOJ-1159：SampleInput

abcfbcabfcab

programmingcontest

abcdmnpSampleOutput

4

2

02022/12/2185五、經(jīng)典問(wèn)題：最長(zhǎng)公共子序列HDOJ-1159：Sample最長(zhǎng)公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長(zhǎng)公共子序列。

2022/12/2186最長(zhǎng)公共子序列若給定序列X={x1,x2,…,xm}，則另一最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。(2)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長(zhǎng)公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長(zhǎng)公共子序列。由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2022/12/2187最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y=子問(wèn)題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：2022/12/2188子問(wèn)題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)abcfbca111111b122222f122333c123334a123334b123344輔助空間變化示意圖2022/12/2189abcfbca111111b122222f122333c12計(jì)算最優(yōu)值由于在所考慮的子問(wèn)題空間中，總共有θ(mn)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}構(gòu)造最長(zhǎng)公共子序列voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}2022/12/2190計(jì)算最優(yōu)值由于在所考慮的子問(wèn)題空間中，總共有θ(mn)個(gè)不同算法的改進(jìn)在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個(gè)值所確定的。如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n))。2022/12/2191算法的改進(jìn)在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組六、經(jīng)典問(wèn)題：1421

搬寢室

ProblemDescription

搬寢室是很累的,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/2192六、經(jīng)典問(wèn)題：1421搬寢室 ProblemDescr六、經(jīng)典問(wèn)題：1421

搬寢室

Input每組輸入數(shù)據(jù)有兩行,第一行有兩個(gè)數(shù)n,k(2<=2*k<=n<2000).第二行有n個(gè)整數(shù)分別表示n件物品的重量(重量是一個(gè)小于2^15的正整數(shù)).

Output對(duì)應(yīng)每組輸入數(shù)據(jù),輸出數(shù)據(jù)只有一個(gè)表示他的最少的疲勞度,每個(gè)一行.2022/12/2193六、經(jīng)典問(wèn)題：1421搬寢室 Inpu