动态规划算法百度百科

动态规划百科名片\o"查看图片"动态规划动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，运用各阶段之间的关系，逐个求解，创建了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。目录简介概念及意义基本模型基本思想基本结构基本模型合用条件作用简介概念及意义基本模型基本思想基本结构基本模型合用条件作用应用动态规划练习题《DynamicProgramming》展开编辑本段简介\o"查看图片"

是信息学竞赛中选手必须纯熟掌握的一种算法,他以其多元性广受出题者的爱慕.动态规划初次进入信息学奥赛是在IOI94（数字三角形），在国内初次出现是在NOI95。此后动态规划成为信息学奥赛的必考算法之一。编辑本段概念及意义动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分派、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划重要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清楚的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，拟定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法对的理解外，必须具体问题具体分析解决，以丰富的想象力去建立模型，用发明性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。编辑本段基本模型多阶段决策过程的最优化问题。具有递推的思想以及各种数学原理（加法原理，乘法原理等等）。在现实生活中，有一类活动的过程，由于它的特殊性，可将过程提成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达成最佳的活动效果。当然，各个阶段决策的选取不是任意拟定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策拟定后，就组成一个决策序列，因而也就拟定了整个过程的一条活动路线，如图所示：（看词条图）\o"查看图片"多阶段决策问题这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。编辑本段基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，也许会有许多可行解。每一个解都相应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被反复计算了很多次。假如我们可以保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的反复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思绪。具体的动态规划算法多种多样，但它们具有相同的填表格式。编辑本段基本结构多阶段决策问题中，各个阶段采用的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清楚的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，拟定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划，可以解决各类最优化问题。因此在学习时，除了要对基本概念和方法对的理解外，必须具体问题具体分析解决，以丰富的想象力去建立模型，用发明性的技巧去求解。编辑本段基本模型根据上例分析和动态规划的基本概念，可以得到动态规划的基本模型如下：(1)拟定问题的决策对象。(2)对决策过程划分阶段。(3)对各阶段拟定状态变量。(4)根据状态变量拟定费用函数和目的函数。(5)建立各阶段状态变量的转移过程，拟定状态转移方程。编辑本段合用条件任何思想方法都有一定的局限性，超过了特定条件，它就失去了作用。同样，动态规划也并不是万能的。合用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不管过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的顺序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将本来具有指数级复杂度的搜索算法改善成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的主线目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。编辑本段作用在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。记忆化搜索给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所通过的权值之和最小或者最大.无论对与新手还是老手，这都是再熟悉但是的题了，很容易地，我们写出状态转移方程：f(i,j)=a[i,j]+min{f(i+1,j)，f(i+1,j+1)}对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表达方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简朴了。解决方法：我们尝试从正面的思绪去分析问题，如上例，不难得出一个非常简朴的递归过程:f1=f(i+1,j+1);f2=f(i+1,j);if(f1>f2)thenf=f2+a[i,j];elsef=f1+a[i,j];显而易见，这个算法就是最简朴的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，事实上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i,j]-每产生一个f(i,j)，将f(i,j)的值放入opt中，以后再次调用到f(i,j)的时候，直接从opt[i,j]来取就可以了。于是动态规划的状态转移方程被直观地表达出来了，这样节省了思维的难度，减少了编程的技巧，而运营时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，并且在相称多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.并且记忆搜索占的内存相对来说较少计算核心片段：for(inti=n-1;i>=1;--i)//从倒数第二行开始{for(intj=1;j<=i;j++){if(a[i+1][j][1]>a[i+1][j+1][1])//左边大{a[i][j][2]=0;//选择左边a[i][j][1]+=a[i+1][j][1];}else//右边大{a[i][j][2]=1;//选择右边a[i][j][1]+=a[i+1][j+1][1];}}}决策决策：当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。状态状态：我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态拟定后,以前状态就已经拟定,则无需枚举.编辑本段应用一、动态规划的概念近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的规定也越来越高，已经不再停留于简朴的递推和建模上了。要了解动态规划的概念，一方面要知道什么是多阶段决策问题。1.多阶段决策问题假如一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采用措施)，一个阶段的决策拟定以后，经常影响到下一个阶段的决策，从而就完全拟定了一个过程的活动路线，则称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，相应于一个策略可以拟定活动的效果，这个效果可以用数量来拟定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达成最佳的效果.2．动态规划问题中的术语阶段：把所给求解问题的过程恰本地提成若干个互相联系的阶段，以便于求解，过程不同，阶段数就也许不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表达。此外，也有阶段变量是连续的情形。假如过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。状态：状态表达每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。\o"查看图片"不可控因素在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的解决将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；并且在每个阶段的状态维数可以不同。\o"查看图片"状态变量当过程按所有也许不同的方式发展时，过程各段的状态变量将在某一拟定的范围内取值。状态变量取值的集合称为状态集合。无后效性：我们规定状态具有下面的性质：假如给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都拟定期，整个过程也就拟定了。换句话说，过程的每一次实现可以用一个状态序列表达，在前面的例子中每阶段的状态是该线路的始点，拟定了这些点的序列，整个线路也就完全拟定。从某一阶段以后的线路开始，当这\o"查看图片"无后效性段的始点给定期，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表达为一个数或一组数。不同的决策相应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。\o"查看图片"允许决策集合策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略\o"查看图片"最优策略集合中达成最优效果的策略称为最优策略。给定k阶段状态变量x(k)的值后，假如这一阶段的决策变量一经拟定，第k+1阶段的状态变量x(k+1)也就完全拟定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么\o"查看图片"状态转移方程可以把这一关系当作(x(k)，u(k))与x(k+1)拟定的相应关系，用x(k+1)=Tk(x(k),u(k))表达。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。最优化原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。一个问题满足最优化原理也称其拥有最优子结构性质。D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：C2B1最优性原理事实上是规定问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D，我们知道，最短途径是A\o"查看图片"最优化原理D也是B1到D的最短途径……──事实正是如此，因此我们认为这个例子满足最优性原理的规定。C2C2是A到C2的最短途径，B1B1编辑本段动态规划练习题USACO2.2SubsetSums题目如下：对于从1到N的连续整集合合，能划提成两个子集合，且保证每个集合的数字和是相等的。举个例子，假如N=3，对于{1，2，3}能划提成两个子集合，他们每个的所有数字和是相等的：{3}and{1,2}这是唯一一种分发（互换集合位置被认为是同一种划分方案，因此不会增长划分方案总数）假如N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:{1,6,7}and{2,3,4,5}{注1+6+7=2+3+4+5}{2,5,7}and{1,3,4,6}{3,4,7}and{1,2,5,6}{1,2,4,7}and{3,5,6}给出N，你的程序应当输出划分方案总数，假如不存在这样的划分方案，则输出0。程序不能预存结果直接输出。PROGRAMNAME:subsetINPUTFORMAT输入文献只有一行，且只有一个整数NSAMPLEINPUT(filesubset.in)7OUTPUTFORMAT输出划分方案总数，假如不存在则输出0。SAMPLEOUTPUT(filesubset.out)4参考程序如下（C++语言）：#include<fstream>usingnamespacestd;constunsignedintMAX_SUM=1024;intn;unsignedlonglongintdyn[MAX_SUM];ifstreamfin("subset.in");ofstreamfout("subset.out");intmain(){fin>>n;fin.close();ints=n*(n+1);if(s%4){fout<<0<<endl;fout.close();return;}s/=4;inti,j;dyn[0]=1;for(i=1;i<=n;i++)for(j=s;j>=i;j--)dyn[j]+=dyn[j-i];fout<<(dyn[s]/2)<<endl;fout.close();return0;}USACO2.3LongestPrefix题目如下：在生物学中，一些生物的结构是用包含其要素的大写字母序列来表达的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感爱好。假如一个集合P中的元素可以通过并运算（允许反复；并，即∪，相称于Pascal中的“+”运算符）组成一个序列S，那么我们认为序列S可以分解为P中的元素。并不是所有的元素都必须出现。举个例子，序列ABABACABAAB可以分解为下面集合中的元素：{A,AB,BA,CA,BBC}序列S的前面K个字符称作S中长度为K的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。PROGRAMNAME:prefixINPUTFORMAT输入数据的开头涉及1..200个元素（长度为1..10）组成的集合，用连续的以空格分开的字符串表达。字母所有是大写，数据也许不止一行。元素集合结束的标志是一个只包含一个“.”的行。集合中的元素没有反复。接着是大写字母序列S，长度为1..200,000，用一行或者多行的字符串来表达，每行不超过76个字符。换行符并不是序列S的一部分。SAMPLEINPUT(fileprefix.in)AABBACABBC.ABABACABAABCOUTPUTFORMAT只有一行，输出一个整数，表达S可以分解成P中元素的最长前缀的长度。SAMPLEOUTPUT(fileprefix.out)11示例程序如下：#include<stdio.h>/*maximumnumberofprimitives*/#defineMAXP200/*maximumlengthofaprimitive*/#defineMAXL10charprim[MAXP+1][MAXL+1];/*primitives*/intnump;/*numberofprimitives*/intstart[202301];/*isthisprefixofthesequenceexpressible?*/chardata[202300];/*thesequence*/intndata;/*lengthofthesequence*/intmain(intargc,char**argv){FILE*fout,*fin;intbest;intlv,lv2,lv3;if((fin=fopen("prim.in","r"))==NULL){perror("fopenfin");exit(1);}if((fout=fopen("prim.out","w"))==NULL){perror("fopenfout");exit(1);}/*readinprimitives*/while(1){fscanf(fin,"%s",prim[nump]);if(prim[nump][0]!='.')nump++;elsebreak;}/*readinstring,onelineatatime*/ndata=0;while(fscanf(fin,"%s",data+ndata)==1)ndata+=strlen(data+ndata);start[0]=1;best=0;for(lv=0;lv<ndata;lv++)if(start[lv]){/*foreachexpressibleprefix*/best=lv;/*wefoundalongerexpressibleprefix!*//*foreachprimitive,determinethethesequencestartingatthislocationmatchesit*/for(lv2=0;lv2<nump;lv2++){for(lv3=0;lv+lv3<ndata&&prim[lv2][lv3]&&prim[lv2][lv3]==data[lv+lv3];lv3++);if(!prim[lv2][lv3])/*itmatched!*/start[lv+lv3]=1;/*sotheexpandedprefixisalsoexpressive*/}}/*seeiftheentiresequenceisexpressible*/if(start[ndata])best=ndata;fprintf(fout,"%i\n",best);return0;}USACO3.1ScoreInflation题目如下：我们试着设计我们的竞赛以便人们能尽也许的多得分,这需要你的帮助。我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职工,应当从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入涉及竞赛的时间,M(1<=M<=10,000)和N,"种类"的数目1<=N<=10,000。后面的每一行将涉及两个整数来描述一个"种类":第一个整数说明解决这种题目能得的分数(1<=points<=10000),第二整数说明解决这种题目所需的时间(1<=minutes<=10000)。你的程序应当拟定我们应当从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。来自任意的"种类"的题目数目也许任何非负数(0或更多)。计算也许得到的最大分数。PROGRAMNAME:inflateINPUTFORMAT第1行:M,N--竞赛的时间和题目"种类"的数目。第2-N+1行:两个整数:每个"种类"题目的分数和耗时。SAMPLEINPUT(fileinflate.in)3004100602501201201003520OUTPUTFORMAT单独的一行涉及那个在给定的限制里也许得到的最大的分数。SAMPLEOUTPUT(fileinflate.out)605{从第2个"种类"中选两题，第4个"种类"中选三题}示例程序如下：#include<fstream.h>ifstreamfin("inflate.in");ofstreamfout("inflate.out");constshortmaxm=10010;longbest[maxm],m,n;voidmain(){shorti,j,len,pts;fin>>m>>n;for(j=0;j<=m;j++)best[j]=0;for(i=0;i<n;i++){fin>>pts>>len;for(j=len;j<=m;j++)if(best[j-len]+pts>best[j])best[j]=best[j-len]+pts;}fout<<best[m]<<endl;//由于数组元素不减，末元素最大}USACO3.3AGame题目如下：有如下一个双人游戏:N(2<=N<=100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者为胜。编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的也许的总分的策略。你的程序要始终为第二位玩家执行最优策略。PROGRAMNAME:game1INPUTFORMAT第一行:正整数N,表达序列中正整数的个数。第二行至末尾:用空格分隔的N个正整数（大小为1-200）。SAMPLEINPUT(filegame1.in)6472952OUTPUTFORMAT只有一行，用空格分隔的两个整数:依次为玩家一和玩家二最终的得分。SAMPLEOUTPUT(filegame1.out)1811参考程序如下：#include<stdio.h>#defineNMAX101intbest[NMAX][2],t[NMAX];intn;voidreadx(){inti,aux;freopen("game1.in","r",stdin);scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&aux);t=t[i-1]+aux;}fclose(stdin);}inlineintmin(intx,inty){returnx>y?y:x;}voidsolve(){inti,l;for(l=1;l<=n;l++)for(i=1;i+l<=n+1;i++)best[l%2]=t[i+l-1]-t[i-1]-min(best[i+1][(l-1)%2],best[(l-1)%2]);}voidwritex(){freopen("game1.out","w",stdout);printf("%d%d\n",best[1][n%2],t[n]-best[1][n%2]);fclose(stdout);}intmain(){readx();solve();writex();return0;}USACO3.4RaucousRockers题目如下：你刚刚得到了流行的“破锣摇滚”乐队录制的尚未发表的N(1<=N<=20)首歌的版权。你打算从中精选一些歌曲，发行M(1<=M<=20)张CD。每一张CD最多可以容纳T(1<=T<=20)分钟的音乐，一首歌不能分装在两张CD中。不巧你是一位古典音乐迷，不懂如何鉴定这些歌的艺术价值。于是你决定根据以下标准进行选择：歌曲必须按照创作的时间顺序在CD盘上出现。选中的歌曲数目尽也许地多。PROGRAMNAME:rockersINPUTFORMAT第一行：三个整数：N,T,M.第二行：N个整数，分别表达每首歌的长度，按创作时间顺序排列。SAMPLEINPUT(filerockers.in)4524342OUTPUTFORMAT一个整数，表达可以装进M张CD盘的乐曲的最大数目。SAMPLEOUTPUT(filerockers.out)3参考程序如下：#include<stdio.h>#defineMAX25intdp[MAX][MAX][MAX],length[MAX];intmain(){FILE*in=fopen("rockers.in","r");FILE*out=fopen("rockers.out","w");inta,b,c,d,best,numsongs,cdlength,numcds;fscanf(in,"%d%d%d",&numsongs,&cdlength,&numcds);for(a=1;a<=numsongs;a++)fscanf(in,"%d",&length[a]);best=0;for(a=0;a<numcds;a++)/*当前cd*/for(b=0;b<=cdlength;b++)/*已过的时间*/for(c=0;c<=numsongs;c++){/*上一曲*/for(d=c+1;d<=numsongs;d++){/*下一曲*/if(b+length[d]<=cdlength){if(dp[a][c]+1>dp[a][b+length[d]][d])dp[a][b+length[d]][d]=dp[a][c]+1;}else{if(dp[a][c]+1>dp[a+1][length[d]][d])dp[a+1][length[d]][d]=dp[a][c]+1;}}if(dp[a][c]>best)best=dp[a][c];}fprintf(out,"%d\n",best);return0;}USACO4.3BuyLow,BuyLower“逢低吸纳”是炒股的一条成功秘诀。假如你想成为一个成功的投资者，就要遵守这条秘诀:"逢低吸纳,越低越买"这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。\o"查看图片"逢低吸纳,越低越买给定连续的N天中天天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。以下面这个表为例,某几天的股价是:天数123456789101112股价686954646864706778629887这个例子中,聪明的投资者(按上面的定义)，假如每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(也许有其他的买法):天数25610股价69686462PROGRAMNAME:buylowINPUTFORMAT第1行:N(1<=N<=5000),表达能买股票的天数。第2行以下:N个正整数(也许分多行)，第i个正整数表达第i天的股价.这些正整数大小不会超过longint(pascal)/long(c++).SAMPLEINPUT(filebuylow.in)12686954646864706778629887OUTPUTFORMAT只有一行，输出两个整数：可以买进股票的天数长度达成这个值的股票购买方案数量在计算解的数量的时候，假如两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案也许产生同一个字符串，这样只能计算一次。SAMPLEOUTPUT(filebuylow.out)42参考程序如下：#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefstructBIGNUM*bignum_t;structBIGNUM{intval;bignum_tnext;};intnum[5000];intlen[5000];intnlen;bignum_tcnt[5000];bignum_tget_big(void){staticbignum_tblock;staticintsize=0;if(size==0){block=(bignum_t)malloc(sizeof(*block)*128);size=128;}size--;returnblock++;}/*初始化高精度数*/voidinit_big(bignum_t*num,intval){*num=get_big();/*initialize*/(*num)->val=val;(*num)->next=NULL;}voidadd(bignum_ta,bignum_tb){intc;/*