动态规划 分类.doc

动态规划分类1、背包模型 包括0-1背包、无限背包、有限背包、有价值背包、小数背包（贪心即可)等，是极为经典的模型，其转化与优化也是很重要的。 H P4 k v3T V A2、最长非降子序列模型 7i _ F+E N H g O8| | | s 改版：渡河问题、合唱队型等 3、最大子段和模型 改版：K大子段和、最佳游览，最大子矩阵和等。 4、LCS模型 ?:p0n E m$v |+r 改版：回文字串、多串的LCS等 5、括号序列模型 M Y3e V D:D 改版：关灯问题（TSOJ）、charexp（TSOJ）、最大算式等，核心思想在于以串的长度为阶段。 6、递推模型 p:l s#U i _1J L 这类题是属于徘徊在DP与递归之间得一类题，本质是类似于记忆化搜索的一种填表，有很强的数学味。 &e n o A:l V7、线段覆盖问题 改版：Tom的烦恼（TOJ）等。经常利用到离散化等技巧辅助。 g R V1e+h&F8、单词划分模型 和LCS基本上构成了字符串DP的主要类型。改版：奇怪的门（TOJ）等。 9、股票模型 8u F. x&m |8g! 这是DP优化的经典模型。改版有换外汇等。 ,o/z yw ?5/d10、连续段划分模型 即要求把数列划分成k个连续段，使每段和的最大值最小。改版有任务调度等。 x0e B6d k X j8tv1| Y11、游戏模型 这类题的阶段（一般是时间）和决策（一般就是游戏目标）很清楚，因此比较容易想到。改版：免费馅饼（NOI98）、Help Jimmy（CEOI2000）、瑰丽华尔兹（NOI2005，优化需要多费功夫）。dp注意的一些总结/sgr123/blog 好好看看看完，做完，想完，总结完后：22/oblog3/user1/40/subject/index.html1.dp一定要边界条件。关于初始值的问题，这是dp的起点，是dp中除方程外最终要的东西，dp过程中的每一个值必须都符合他的状态所表示的意义，否则就是错的，以前方程写对了，但是在这个问题上却经常出错，看了dd_engi大牛的背包问题九讲中关于背包恰好放满，与可不放满的最大值大求法的比较后才恍然大悟，除非所有的初始边界在此状态定义下他的有意义的值就是0，否则必须初始化。例如背包。（初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。背包问题九讲）2.初始最小值不要想当然的赋0，有时候要求的值可能是负的，一定要看清题意，注意赋-，但是再用计算机表示的时候不要赋的过大，或过小，因为中间的运算过程中可能会中间值越界产生215错误而爆掉3.递推顺序每一步怎样取最大值，以及每一步的值对后来有什么影响都要考虑全再开始编，不要一出来方程就动手4.先考虑清楚，必须一次ac！5.始终遵循dp每一步都只用已经算出来的！拿到一个题一定要 先想好 数据结构（在纸上写好），算 法框架（最好也在纸上写好）胸有成竹再下笔！否则则只是浪费时间！6.不要想当然的把所有的最优化的题目都认为是dp，往往贪心和模拟能够发挥巨大作用！不是dp的题用dp去做，绝对是错误的！7.不是动归方程写出来就万事大吉了，必须能证明它的无后效性，必须满足最有子结构，过于复杂的方程往往是错误的，即使分类考虑的情况很多，但是每一类也应该很简洁，必须证明它的正确性再动手，否则是在白费力气。8.一定要考虑全面，动归方程一定要包含所有的情况。9.再说一遍！实现的时候一定要注意递推边界和循环范围，每一步用到的值都是已经求出来的，初始化！动态规划一、多阶段决策过程的最优化问题问题的提出首先，例举一个典型的且很直观的多阶段决策问题:例 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A-E。求A-E的最省费用。如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择，一是走到B1，一是走到B2，一是走到B3。若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合(C1，C2，C3)；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就不同。很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。具体情况如下：（1）由目标状态E向前推，可以分成四个阶段，即四个子问题。如上图所示。（2）策略：每个阶段到E的最省费用为本阶段的决策路径。（3）D1，D2是第一次输入的结点。他们到E都只有一种费用，在D1框上面标5，D2框上面标2。目前无法定下，那一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算。（4）C1，C2，C3是第二次输入结点，他们到D1，D2各有两种费用。此时应计算C1，C2，C3分别到E的最少费用。C1的决策路径是 min（C1D1），（C1D2）。计算结果是C1+D1+E，在C1框上面标为8。同理C2的决策路径计算结果是C2+D2+E，在C2框上面标为7。同理C3的决策路径计算结果是C3+D2+E，在C3框上面标为12。此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上。（5）第三次输入结点为B1，B2，B3，而决策输出结点可能为C1，C2，C3。仿前计算可得B1，B2，B3的决策路径为如下情况。B1:B1C1费用 12+8=20， 路径:B1+C1+D1+EB2:B2C1费用 6+8=14， 路径:B2+C1+D1+EB3:B2C2费用 12+7=19， 路径:B3+C2+D2+E此时也无法定下第一，二，三阶段的城市那三个将在整体的最优决策路径上。（6）第四次输入结点为A，决策输出结点可能为B1，B2，B3。同理可得决策路径为A：AB2，费用5+14=19，路径 A+B2+C1+D1+E。此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。19是结果，显然这种计算方法，符合最优原理。子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去决定。二、动态规划的概念在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。与穷举法相比，动态规划的方法有两个明显的优点:(1)大大减少了计算量(2)丰富了计算结果从上例的求解结果中，我们不仅得到由A点出发到终点E的最短路线及最短距离，而且还得到了从所有各中间点到终点的最短路线及最短距离，这对许多实际问题来讲是很有用的。动态规划的最优化概念：是在一定条件下，得到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。三、动态规划适合解决什么样的问题准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。上面所说的“满足一定条件”主要指下面两点：(1)状态必须满足最优化原理；(2)状态必须满足无后效性。动态规划的最优化原理：是无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优。在上例中例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。动态规划的无后效性原则：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。为什么要用动态规划法解题首先，看下面一个问题:【例题1】数字三角形问题。 7 3 8 8 1 0 2 7 7 4 5 5 2 6 5显示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。如输入： 57 3 8 8 1 0 2 7 7 4 4 5 2 6 5 输出：30【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序如下：program sjx;const maxn=10;vara:array1.maxn,1.maxn of integer;max:longint;n,i,j:integer;fname:string;inputf:text;procedure try(x,y,dep:integer;sum:longint);begin if (dep=n) then begin if summax then max:=sum; exit end; try(x+1,y,dep+1,sum+ax+1,y); try(x+1,y+1,dep+1,sum+ax+1,y+1);end;beginreadln(fname);assign(inputf,fname);reset(inputf);readln(inputf,n);for i:=1 to n do for j:= 1 to i do read(inputf,ai,j);max:=0;try(1,1,1,a1,1);writeln(max);end.但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。二、怎样用动态规划法解题1.逆推法:按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段第1阶段(起始点)各决策点至第n行的最佳路径。设：fi,j为从第i阶段中的点j至第n行的最大的数字和；则: fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=jfi+1,j+1 then fi,j:=ai,j+fi+1,j else fi,j:=ai,j+fi+1,j+1;writeln(f1,1);end. 2. 顺推法按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和,再依次求出第3,4，5,.,.n-1,n到起点的最大和,最后找第n行的最大值设fi,j为 第i行第j列上点到起点的最大和则 f1，1=a1,1; fi，1=ai, 1+fi-1,1; f i，j =max ai,j+fi-1,j-1,ai,j+fi-1,j 2=jfi-1,j then fi,j:=ai,j+fi-1,j-1 else fi,j:=ai,j+fi-1,j; end;maxsum:=0;for i:=1 to n do if fn,imaxsum then maxsum:=fn,i;writeln(maxsum);end.说明一下：1.用动态规划解题主要思想是用空间换时间.2.本题如果n较大，用2维数组空间可能不够,可以使用1维数组.程序如下:program datasjx;const maxn=100;varfname:string;inputf:text;n,i,j:integer;a:array1.maxn,1.maxn of integer;f:array1.maxn of integer;maxsum:integer;beginreadln(fname);assign(inputf,fname);reset(inputf);readln(inputf,n);for i:=1 to n do for j:=1 to i do read(inputf,ai,j);fillchar(f,sizeof(f),0);f1:=a1,1;for i:=2 to n do begin for j:=i downto 2 do if fj-1fj then fj:=ai,j+fj-1 else fj:=ai,j+fj; f1:=ai,1+f1; end;maxsum:=0;for i:=1 to n do if fimaxsum then maxsum:=fi;writeln(maxsum);end.练习:用一维数组和逆推法解本题.三、用动态规划法解题的一般模式动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。初始状态决策决策决策结束状态(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据上述动态规划设计的步骤，可得到大体解题框架如下:1.初始化(边界条件)2.for i:=2 to n (顺推法) 或 for i:=n-1 to 1(逆推法) 对i阶段的每一个决策点求局部最优3.确定和输出结束状态的值.第三章 典型例题与习题3.1 最长不降子序列3.2 背包问题3.3 最短路径3.1 最长不降子序列（1）问题描述设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)且a(i)a(j) (ij)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3 ie 且有a(i1)a(i2) a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。（2）算法分析根据动态规划的原理，由后往前进行搜索。1 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；2 若从a(n-1)开始查找，则存在下面的两种可能性：若a(n-1)a(n)则存在长度为1的不下降序列a(n-1)或a(n)。3 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:在a(i+1),a(i+2),a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号(3) 程序如下:（逆推法）program li1;const maxn=100;var a,b,c:array1.maxn of integer; fname:string; f:text; n,i,j,max,p:integer;beginreadln(fname);assign(f,fname);reset(f);readln(f,n);+for i:=1 to n do begin read(f,ai); bn:=1; cn:=0; end;for i:= n-1 downto 1 do begin max:=0;p:=0; for j:=i+1 to n do if (aimax) then begin max:=bj;p:=j end; if p0 then begin bi:=bp+1;ci:=p end end;max:=0;p:=0;for i:=1 to n do if bimax then begin max:=bi;p:=i end;writeln(maxlong=,max);write(result is:);while p0 do begin write(ap:5);p:=cp end;end.3.2 背包问题背包问题有三种1.部分背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，.,Wn,它们的总价值分别为C1,C2,.,Cn.求旅行者能获得最大总价值。 解决问题的方法是贪心算法:将C1/W1,C2/W2,.Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止. 2.0/1背包 一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，.,Wn,它们的价值分别为C1,C2,.,Cn.若每种物品只有一件求旅行者能获得最大总价值。 分析说明: 显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制). 程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数 设 f(i，x)表示前i件物品，总重量不超过x的最优价值 则 f（i，x）=max(f(i1，x-Wi)+Ci，f（i1，x） f（n，m）即为最优解，边界条件为f（0，x）0 ，f(i,0)=0; 动态规划方法(顺推法)程序如下: 程序如下： program knapsack02;const maxm=200;maxn=30;type ar=array1.maxn of integer;var m,n,j,i:integer;c,w:ar;f:array0.maxn,0.maxm of integer;function max(x,y:integer):integer;begin if xy then max:=x else max:=y;end;begin readln(m,n); for i:= 1 to n do readln(wi,ci); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j=wi then fi,j:=max(fi-1,j-wi+ci,fi-1,j) else fi,j:=fi-1,j; end; writeln(fn,m); end. 使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。 3.完全背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，.,Wn,每件的价值分别为C1,C2,.,Cn.若的每种物品的件数足够多.求旅行者能获得的最大总价值。本问题的数学模型如下： 设 f(x)表示重量不超过x公斤的最大价值， 则 f(x）=maxf(x-wi)+ci 当x=wi 1=i=wj then t:=fi-wj+cj; if tfi then fi:=t end; writeln(fm); end.3.3 最短路径问题描述：如图：求v1到v10的最短路径长度及最短路径。图的邻接矩阵如下：0 2 5 1 -1 -1 -1 -1 -1 -1-1 0 -1 -1 12 14 -1 -1 -1 -1-1 -1 0 -1 6 10 4 -1 -1 -1-1 -1 -1 0 13 12 11 -1 -1 -1-1 -1 -1 -1 0 -1 -1 3 9 -1-1 -1 -1 -1 -1 0 -1 6 5 -1-1 -1 -1 -1 -1 -1 0 -1 10 -1-1 -1 -1 -1 -1 -1 -1 0 -1 5-1 -1 -1 -1 -1 -1 -1 -1 0 2-1 -1 -1 -1 -1 -1 -1 -1 -1 0采用逆推法设f（x）表示点x到v10的最短路径长度则 f(10)=0 f(x)=min f(i)+ax,i 当ax,i0 ,xi0) and (bjmaxint) and (bj+ai,jbi) then begin bi:=bj+ai,j;ci:=j end;writeln(minlong=,b1);x:=1; while x0 do begin write(x:5); x:=cx; end;end.3.4习题1.若城市路径示意图如下图所示:图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。2.求一个数列中的连续若干个数和的最大值.3.资源分配问题:n个资源分配到m个项目上，i项目分配j个资源可获益ai,j,求最大总效益。4. 装箱问题问题描述:有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 样例 输入： 24 一个整数，表示箱子容量 6 一个整数，表示有n个物品 8 接下来n行，分别表示这n 个物品的各自体积 3 12 7 9 7输出：0一个整数，表示箱子剩余空间。图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。2.求一个数列中的连续若干个数和的最大值.3.资源分配问题:n个资源分配到m个项目上，i项目分配j个资源可获益ai,j,求最大总效益。4. 装箱问题问题描述:有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 样例 输入： 24 一个整数，表示箱子容量 6 一个整数，表示有n个物品 8 接下来n行，分别表示这n 个物品的各自体积 3 12 7 9 7输出：0一个整数，表示箱子剩余空间。第四章 动态规划的递归函数法（你实在觉得你动态规划不行，最后1，2个月专攻的算法，平时训练不要当作动态规划的重点，只能是一般算法）4.1 原始递归法4.2 改进递归法4.3 习题4.1 原始递归法先看完全背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，.,Wn,每件的价值分别为C1,C2,.,Cn.若的每种物品的件数足够多.求旅行者能获得的最大总价值。本问题的数学模型如下： 设 f(x)表示重量不超过x公斤的最大价值， 则 f(x）=maxf(x-i)+ci 当x=wi 1=i=wi then m:=f(x-i)+ci; if mt then t:=m; end; f:=t; end;end;begin readln(m,n); for i:= 1 to n do readln(wi,ci); writeln(f(m); end.说明:当m不大时,编程很简单,但当m较大时,容易超时.4.2 改进的递归法改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个一维数组即可程序如下:program knapsack04;const maxm=2000;maxn=30;type ar=array0.maxn of integer;var m,n,j,i,t:integer;c,w:ar;p:array0.maxm of integer;function f(x:integer):integer;var i,t,m:integer;beginif px-1 then f:=px else begin if x=0 then px:=0 else begin t:=-1; for i:=1 to n do begin if x=wi then m:=f(i-wi)+ci; if mt then t:=m; end; px:=t; end; f:=px;end;end;begin readln(m,n); for i:= 1 to n do readln(wi,ci);fillchar(p,sizeof(p),-1); writeln(f(m); end.4.3习题 用改进的递归法解资源分配问题:n个资源分配到m个项目上，i项目分配j个资源可获益ai,j,求最大总效益。5.1 例1乘积最大问题问题描述：今年是国际数学联盟确定的2000-世界数学年，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手除了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字川：312，当N=3,K=1时会有一下两种分法：1） 3*12=362） 31*2=62这时，符合题目要求的结果是；31*2=62现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。输入：程序的输入共有两行：第一行共有2个自然数N，K（6N50，1K20）第二行是一个长度为N的数字串。输出：结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。样例：输入4 21231输出62 程序如下：program tg20002;const maxn=50;maxk=20 ;type num=record len:byte; s:array1.maxn of byte; end;type str=stringmaxn;var n,k,i,j,l:integer; st,temps:str; m,tempm:num; f:array1.maxn of num; s1:array1.maxn of str;procedure strtonum(str1:str;var num1:num);var i:integer;beginnum1.len:=length(str1);for i:=1 to num1.len do num1.si:=ord(str1num1.len-i+1)-ord(0);end;procedure mult(x,y:num;var z: num );var i,j,len:integer;beginfillchar(z,sizeof(z),0);for i:= 1 to x.len do for j:=1 to y.len do begin inc(z.si+j-1, x.si*y.sj); inc(z.si+j,z.si+j-1 div 10); z.si+j-1:=z.si+j-1 mod 10; end;len:=x.len+y.len+1;while (len1) and (z.slen=0) do len:=len-1;z.len:=len;end;procedure bigger(x,y:num;var z:num);var i:integer;beginif x.leny.len then begin z.len:=x.len;z.s:=x.s end elseif x.len1) and (x.si=y.si) do i:=i-1; if x.si=y.si then z.s:=x.s else z.s:=y.s;end;end;beginreadln(n,k);readln(st);fillchar(f,sizeof(f),0);for i:=1 to n do begin s1i:=copy(st,1,i); strtonum(s1i,fi); end;for i:=2 to k+1 do for j:=n