最新-C案例04动态规划-课件

第四讲动态规划（Dynamicprogramming）2022/12/211第四讲动态规划2022/12/171一、经典问题：数塔问题

有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。2022/12/212一、经典问题：数塔问题 有形如下图所示的用暴力的方法，可以吗？2022/12/213用暴力的方法，可以吗？2022/12/173 这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3>10^9=10亿）。试想一下：2022/12/214 这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如

拒绝暴力，倡导和谐～2022/12/215拒绝暴力，倡导和谐～2022/12/175

从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。 同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。 如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。

结论：自顶向下的分析，自底向上的计算。考虑一下：2022/12/216 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最

思路：从倒数第二行起，按照状态转移方程dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+val[i][j]向上递推，直到val[1][1]，此时dp[1][1]就是结果2022/12/217 思路：从倒数第二行起，按照状态转移方程2022/12/1二、经典问题：最长有序子序列[问题描述]

找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列

（注：这里有序指非递减顺序，且不要求子序列连续）。

例如，对于序列[3,7,1,5,9,3]，其中最长有序子序列长度为3，这样的子序列有：

[3,7,9]、[1,5,9]、[3,5,9]。2022/12/218二、经典问题：最长有序子序列[问题描述]

找出由n个二、经典问题：最长有序子序列

2022/12/219二、经典问题：最长有序子序列

2022/12/179二、经典问题：最长有序子序列2022/12/2110二、经典问题：最长有序子序列2022/12/1710二、经典问题：最长有序子序列2022/12/2111二、经典问题：最长有序子序列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

解题思路：题目要求找到的体重递增，速度递减老鼠，先把老鼠的体重进行升序排序然后算出速度的最长递减子序列。

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动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022/12/2120动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想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但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想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如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。2022/12/2123动态规划基本步骤找出最优解的性质，并刻划其结构特征。2022动态规划算法的基本要素一、最优子结构问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）2022/12/2124动态规划算法的基本要素一、最优子结构问题的最优解包含着其子动态规划算法的基本要素二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。2022/12/2125动态规划算法的基本要素二、重叠子问题递归算法求解问题时，每次动态规划算法的基本要素三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。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动态规划算法的基本要素三、备忘录方法备忘录方法的控制结构与直五、经典问题：最长公共子序列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五、经典问题：最长公共子序列ProblemDescript五、经典问题：最长公共子序列HDOJ-1159：SampleInput

abcfbcabfcab

programmingcontest

abcdmnpSampleOutput

4

2

02022/12/2128五、经典问题：最长公共子序列HDOJ-1159：Sample最长公共子序列若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

2022/12/2129最长公共子序列若给定序列X={x1,x2,…,xm}，则另一最长公共子序列的结构设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。2022/12/2130最长公共子序列的结构设序列X={x1,x2,…,xm}和Y=子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：2022/12/2131子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问abcfbca111111b122222f122333c123334a123334b123344辅助空间变化示意图2022/12/2132abcfbca111111b122222f122333c12计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。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;}}}构造最长公共子序列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计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同算法的改进在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。2022/12/2134算法的改进在算法lcsLength和lcs中，可进一步将数组六、经典问题：1421

搬寝室

ProblemDescription

搬寝室是很累的,xhd深有体会.时间追述2019年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2=9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.2022/12/2135六、经典问题：1421搬寝室 ProblemDescr六、经典问题：1421

搬寝室

Input每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).

Output对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.2022/12/2136六、经典问题：1421搬寝室 Input2022/12/六、经典问题：1421

搬寝室

SampleInput

21

13

SampleOutput

42022/12/2137六、经典问题：1421搬寝室 SampleInput2第一感觉：根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？证明：假设四个从小到大的数：a、b、c、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第一感觉：根据题目的要求，每次提的两个物品重量差越小越好，是预备工作：排序！2022/12/2139预备工作：排序！2022/12/1739第二感觉：对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？请思考…考虑以下情况：

1458什么结论？2022/12/2140第二感觉：对于一次操作，显然提的物品重量越接近越好，是不是可详细分析：从最简单的情况考虑：2个物品选一对，结论显然结论？4个物品选一对？（如何利用前面的知识）3个物品选一对，…n个物品选一对，…最终问题：n个物品选k对（n>=2k），如何？n个物品选二对，…2022/12/2141详细分析：从最简单的情况考虑：结论？4个物品选一对？（如何利解题思路先对物品的重量进行排序，取相邻的物品，将相邻的物品的差的平方另外存储，得到状态转移方程：dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]),s[i]是代表i,i+1这两个物品的疲惫度.因为s[i-1],s[i].代表的是ai-1,ai,ai+1的疲惫度，中间共享了一个ai，所以第二项要用dp[i-2].2022/12/2142解题思路先对物品的重量进行排序，取相邻的物品，将相邻的物品的参考代码#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七、经典问题：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七、经典问题：1058HumbleNumbers Pr七、经典问题：1058HumbleNumbers

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

OutputForeachtestcase,printonelinesaying"Thenthhumblenumberisnumber.".Dependingonthevalueofn,thecorrectsuffix"st","nd","rd",or"th"fortheordinalnumbernthhastobeusedlikeitisshowninthesampleoutput.2022/12/2145七、经典问题：1058HumbleNumbers In七、经典问题：1058HumbleNumbers

2022/12/2146七、经典问题：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,状态转移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7) (n>i,j,k,m)特别的：

i,j,k,m只有在本项被选中后才移动2022/12/2148状态转移方程？F(n)=min(F(i)*2,F(j)*3,关键问题：这个题目的哪些经验值得我们借鉴？2022/12/2149关键问题：这个题目的哪些经验值得我们借鉴？2022/12/1八免费馅饼

11762022/12/2150八免费馅饼11762022/12/1750八免费馅饼

1176ProblemDescription都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）2022/12/2151八免费馅饼1176ProblemDescription八免费馅饼

1176Input输入数据有多组。每组数据的第一行为以正整数n(0<n<100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。

Output每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。

提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。2022/12/2152八免费馅饼1176Input2022/12/1752八免费馅饼

1176SampleInput65141617272830

SampleOutput42022/12/2153八免费馅饼1176SampleInput2022/12如何解决？请发表见解2022/12/2154如何解决？请发表见解2022/12/1754解题思路有点类似于数塔Dp[t][i]=MAX(Dp[t-1][i-1],Dp[t-1][i],Dp[t-1][i+1])+DATA[t][i];2022/12/2155解题思路有点类似于数塔Dp[t][i]=MAX(Dp[t-1自学题请大家自学课本P239最短路径问题P247插入乘号问题2022/12/2156自学题请大家自学课本2022/12/1756

如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。

由此而来的基本思路是——用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。小结：DP的基本思想

2022/12/2157 如果各个子问题不是独立的，不同的子问题的个数只是多项式量第四讲动态规划（Dynamicprogramming）2022/12/2158第四讲动态规划2022/12/171一、经典问题：数塔问题

有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。2022/12/2159一、经典问题：数塔问题 有形如下图所示的用暴力的方法，可以吗？2022/12/2160用暴力的方法，可以吗？2022/12/173 这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3>10^9=10亿）。试想一下：2022/12/2161 这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如

拒绝暴力，倡导和谐～2022/12/2162拒绝暴力，倡导和谐～2022/12/175

从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。 同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。 如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。

结论：自顶向下的分析，自底向上的计算。考虑一下：2022/12/2163 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最

思路：从倒数第二行起，按照状态转移方程dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+val[i][j]向上递推，直到val[1][1]，此时dp[1][1]就是结果2022/12/2164 思路：从倒数第二行起，按照状态转移方程2022/12/1二、经典问题：最长有序子序列[问题描述]

找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列

（注：这里有序指非递减顺序，且不要求子序列连续）。

例如，对于序列[3,7,1,5,9,3]，其中最长有序子序列长度为3，这样的子序列有：

[3,7,9]、[1,5,9]、[3,5,9]。2022/12/2165二、经典问题：最长有序子序列[问题描述]

找出由n个二、经典问题：最长有序子序列

2022/12/2166二、经典问题：最长有序子序列

2022/12/179二、经典问题：最长有序子序列2022/12/2167二、经典问题：最长有序子序列2022/12/1710二、经典问题：最长有序子序列2022/12/2168二、经典问题：最长有序子序列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

解题思路：题目要求找到的体重递增，速度递减老鼠，先把老鼠的体重进行升序排序然后算出速度的最长递减子序列。

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动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022/12/2177动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想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但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想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如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。2022/12/2180动态规划基本步骤找出最优解的性质，并刻划其结构特征。2022动态规划算法的基本要素一、最优子结构问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）2022/12/2181动态规划算法的基本要素一、最优子结构问题的最优解包含着其子动态规划算法的基本要素二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。2022/12/2182动态规划算法的基本要素二、重叠子问题递归算法求解问题时，每次动态规划算法的基本要素三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。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动态规划算法的基本要素三、备忘录方法备忘录方法的控制结构与直五、经典问题：最长公共子序列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五、经典问题：最长公共子序列ProblemDescript五、经典问题：最长公共子序列HDOJ-1159：SampleInput

abcfbcabfcab

programmingcontest

abcdmnpSampleOutput

4

2

02022/12/2185五、经典问题：最长公共子序列HDOJ-1159：Sample最长公共子序列若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

2022/12/2186最长公共子序列若给定序列X={x1,x2,…,xm}，则另一最长公共子序列的结构设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。2022/12/2187最长公共子序列的结构设序列X={x1,x2,…,xm}和Y=子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：2022/12/2188子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问abcfbca111111b122222f122333c123334a123334b123344辅助空间变化示意图2022/12/2189abcfbca111111b122222f122333c12计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。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;}}}构造最长公共子序列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计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同算法的改进在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。2022/12/2191算法的改进在算法lcsLength和lcs中，可进一步将数组六、经典问题：1421

搬寝室

ProblemDescription

搬寝室是很累的,xhd深有体会.时间追述2019年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2=9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.2022/12/2192六、经典问题：1421搬寝室 ProblemDescr六、经典问题：1421

搬寝室

Input每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).

Output对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.2022/12/2193六、经典问题：1421搬寝室 Inpu