《经典算法分析与设计教学案例.ppt》由会员分享，可在线阅读，更多相关《经典算法分析与设计教学案例.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 动态规划 Those who cannot remember the past are doomed to repeat itGeorge Santayana 1 学习要点学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。2通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏；
2、（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。3n动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=4n但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(
3、n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)5n如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2n/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)T(
4、n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)6求组合数求组合数每次求解可将其分为两个子问题的和。把 按递推式分解得到。7首先，将的位置上以及0的位置上元素皆填为1。填某一中间表目时，只要把它右边表目的元素与右下方表目的元素之和填入即可。这样，很快就能求出 10。8动态规划解决问题的基本特征1.动态规划一般解决最值（最优，最大，最小，最长）问题；2.动态规划解决的问题一般是离散的，可以分解（划分阶段）的；3.动态规划解决的问题必须包含最优子结构，即可以由（n1）的最优推导出n的最优9动态规划基本步骤n找出最优解的性质，并刻划其结构特征。n递归地定义最优值。n以自底
5、向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。10矩阵连乘问题n给定n个矩阵 ，其中 与 是可乘的，。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积11（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000,10500,36000,87500,34500u完全加括号的矩阵连乘积可
6、递归地定义为：u设有四个矩阵 ，它们的维数分别是：u总共有五中完全加括号的方式完全加括号的矩阵连乘积12矩阵连乘问题给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：13
7、矩阵连乘问题u穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为Ai:j，这里ij 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量14n特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。n矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。分析最优解的结构15建立递归关系n设计算Ai:j，1ijn
8、，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时，n可以递归地定义mi,j为：这里 的维数为 的位置只有 种可能16计算最优值n对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多次许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算
9、，最终得到多项式时间的算法。17用动态规划法求最优解void MatrixChain(int*p，int n，int*m，int*s)for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t 0)return mij;if(i=j)return 0;int u=LookupChain(i，i)+LookupChain(i+1，j)+pi-
10、1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;21最长公共子序列n一个给定序列的一个给定序列的子序列子序列是在该序列中删去若干元素后得到的是在该序列中删去若干元素后得到的序列。序列。n给定两个序列给定两个序列X和和Y，当另一序列当另一序列Z既是既是X的子序列又是的子序列又是Y的子的子序列时，称序列时，称Z是序列是序列X和和Y的的公共子序列。公共子序列。n最长公共子序列最长公共子序列:公共子序列中长度最长
11、的子序列。公共子序列中长度最长的子序列。n最长公共子序列问题最长公共子序列问题 给定两个序列给定两个序列X=x1,x2,xm和和Y=y1,y2,yn，找出找出X和和Y的一个最长公共子序列。的一个最长公共子序列。n例如例如:X=(A,B,C,B,D,A,B)X的子序列的子序列:q所有所有X的子集的子集(集合中元素按原来在集合中元素按原来在X中的顺序排列中的顺序排列)(A,B,D),(B,C,D,B),等等等等.22最长公共子序列X=(A,B,C,B,D,A,B)X=(A,B,C,B,D,A,B)Y=(B,D,C,A,B,A)Y=(B,D,C,A,B,A)n(B,C,B,A)和(B,D,A,B)都
12、是X和Y 的最长公共子序列(长度为4)n但是,(B,C,A)就不是X和Y的最长公共子序列例：例：23最长公共子序列n对于每一个Xm的子序列,验证它是否是Yn的子序列.nXm有2m个子序列n每个子序列需要o(n)的时间来验证它是否是Yn的子序列.q从Yn的第一个字母开始扫描下去,如果不是则从第二个开始n运行时间:o(n2m)穷举法:24最长公共子序列的结构设序列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)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。
13、(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。25子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：26计算最优值 由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上
14、地计算最优值能提高算法的效率。矩阵 bi,j 告诉我们要获得最优结果应该如何选择:l 如果 xi=yj bi,j=1l 如果 ci-1,j ci,j-1 bi,j=2 否则 bi,j=3void LCSLength(int m，int n，char*x，char*y，int*c，int*b)int i，j;for(i=1;i=m;i+)ci0=0;for(i=0;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;00000000000yj:DACFABxij012nm12033CDc
15、i,j-1ci-1,ji27计算最优值X=(A,B,C,B,D,A,B)Y=(B,D,C,A,B,A)0126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111 2211 2222 1122 331 222331232 3 4 1223 44如果 xi=yj bi,j=“”如果 ci-1,jci,j-1bi,j=“”否则bi,j=“”例:28构造最优解构造最长公共子序列构造最长公共子序列void LCS(int i，int j，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，
16、b);coutxi;else if(bij=2)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);29最大子段和n问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,.,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。q依此定义，所求的最优值为：例如，当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时，最大子段和为：30最大子段和1.一个简单算法一个简单算法int MaxSum(int n,a,&besti,&bestj)int sum=0;for(i=1;i=n;i+)for(j=1;j=n;j+)int t
17、hissum=0;for(k=i;ksum)sum=thissum;besti=i;Bestj=j;return sum;n算法有3重循环，复杂性为O(n3)。n由于有：n算法可作如下改进：int MaxSum(int n,a,&besti,&bestj)int sum=0;for(i=1;i=n;i+)int thissum=0;for(j=i;jsum)sum=thissum;besti=i;bestj=j;n改进后的算法复杂性为O(n2)。31最大子段和2.分治方法求解分治方法求解n从问题的解的结构可以看出，它适合于用分治策略求解：q如果将所给的序列a1:n分为长度相等的两段a1:n/2
18、和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有三种情形：A.a1:n的最大子段和与的最大子段和与a1:n/2的最大子段和相同；的最大子段和相同；B.a1:n的最大子段和与的最大子段和与an/2+1:n的最大子段和相同；的最大子段和相同；C.a1:n的最大子段和为下面的形式。的最大子段和为下面的形式。qA、B这两种情形可递归求得。对于情形C，容易看出，an/2与an/2+1在最优子序列中。因此，我们可以在a1:n/2和an/2+1:n中分别计算出如下的s1和s2。则s1+s2即为出现情形C使得最优值。q int MaxSubSum(int a,int left,int
19、right)int sum=0;if(left=right)sum=aleft0?aleft:0;elseint center=(left+right)/2;int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,center+1,right);int s1=0;lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;int s2=0;rights=0;for(int i=center+1;is2)s2=rights;sum=s1+s2;if(sumle
20、ftsum)sum=leftsum;if(sum0 时 bj=bj-1+aj，否则 bj=aj。由此可得 bj的动态规划递归式:bj=maxbj-1+aj，aj，1jn。n据此，可设计出求最大子段和的动态规划算法如下：int MaxSum(int n,int a)int sum=0;b=0;for(i=1;i0)b+=ai;else b=ai;if(bsum)sum=b;return sum;n显然该算法的计算时间为O(n)。33凸多边形最优三角剖分用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称
21、为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。34三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图(a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所
22、示的语法树表示。矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。35最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P=v0,v1,vn的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优
23、三角剖分的矛盾。36最优三角剖分的递归结构定义tij，1ijn为凸子多边形vi-1,vi,vj的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形vi-1,vi具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t1n。tij的值可以利用最优子结构性质递归地计算。当j-i1时，凸子多边形至少有3个顶点。由最优子结构性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置。由此，tij可递归地定义为：37最
24、优三角剖分的递归结构凸n+1边形P=v0,v1,.,vn的最优三角剖分动态规划算法MinWT：void MinWT(int n,type*t,int*s)for(int i=1;i=n;i+)tii=0;for(int r=2;r=n;r+)for(i=1;i=n;i+)int j=i+r-1;tij=tii+ti+1j+w(i-1,i,j);sij=i;for(int k=i+1;kj;k+)int u=tik+tk+1j+w(i-1,k,j);if(u2n时，算法需要(n2n)计算时间。40电路布线在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,(i)将上端接线柱与
25、下端接线柱相连，如图所示。其中(i)是1,2,n的一个排列。导线(i,(i)称为该电路板上的第i条连线。对于任何1i(j)。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=(i,(i),1in的最大不相交子集。41电路布线最优子结构性质最优子结构性质42电路布线(1)当i=1时(2)当i1时void MNS(C,n,*size)void MNS(C,n,*size)for(j=0;jC1;j+)size1j=0;for(j=0;jC1;j+)size1j=0;for(j=C1;j=n;j+)size1j=0;for(j=C1;j=
26、n;j+)size1j=0;for(i=2;in;i+)for(i=2;in;i+)for(j=0;j for(j=0;jCiCi;j+);j+)sizeijsizeij=sizei-1j;=sizei-1j;for(j=for(j=CjCj;j=n;j+);j1;i-)if(sizeij!=sizei-1j Netm+=i;j=Ci-1;if(j=C1)Netm+=1;43最优二叉搜索树n二叉搜索树（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3 它的左、右子树也分别为二叉排序树45125333724
27、100619078在随机的情况下，二叉查找树的平均查找长度和 是等数量级的44n搜索成功与不成功的概率n二搜索树的期望耗费n有 个节点的二叉树的个数为：n穷举搜索法的时间复杂度为指数级二叉搜索树的期望耗费45二叉搜索树的期望耗费示例46最优二叉搜索树最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为注意到，可以得到O(n2)的算法47多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成
28、的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。48最优子结构性质在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j)可表示为vi，opi+1，vi+j-1。如果这条链
29、的最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链分割为2个子链p(i，s)和p(i+s，j-s)。设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有am1b，cm2d(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。49图像压缩图象的变位压缩存储格式将所
30、给的象素点序列p1,p2,pn,0pi255分割成m个连续段S1,S2,Sm。第i个象素段Si中(1im)，有li个象素,且该段中每个象素都只用bi位表示。设 则第i个象素段Si为设 ，则hibi8。因此需要用3位表示bi,如果限制1li255，则需要用8位表示li。因此，第i个象素段所需的存储空间为li*bi+11位。按此格式存储象素序列p1,p2,pn，需要 位的存储空间。图象压缩问题要求确定象素序列p1,p2,pn的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。50图像压缩设li，bi，是p1,p2,pn的最优分段。显而易见，l1，b1是p1,pl1的最优分段，
31、且li，bi，是pl1+1,pn的最优分段。即图象压缩问题满足最优子结构性质。设si，1in，是象素序列p1,pn的最优分段所需的存储位数。由最优子结构性质易知：其中算法复杂度分析：算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个算法所需的计算时间为O(n)。51流水作业调度n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M
32、1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。分析：分析：直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N=1，2，n。SN是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。52流水作业调度设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器M2的等待时间为b(1)时，安排作业(2)，(n)所需的
33、时间。记S=N-(1)，则有T=T(S,b(1)。证明：证明：事实上，由T的定义知TT(S,b(1)。若TT(S,b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度。则(1)，(2)，(n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S,b(1)。这就证明了流水作业调度问题具有最优子结构的性质。由流水作业调度问题的最优子结构性质可知，53Johnson不等式对递归式的深入分析表明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i,(2)=j。则
34、由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足JohnsonJohnson不等式不等式。54流水作业调度的Johnson法则交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji)其中，当作业i和j满足Johnson不等式时，有由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度，使得作业(i)和(i+1)满
35、足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意ij有由此可知，所有满足所有满足JohnsonJohnson法则的调度均为最优调度。法则的调度均为最优调度。55算法描述流水作业调度问题的Johnson算法(1)令(2)将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序；(3)N1中作业接N2中作业构成满足Johnson法则的最优调度。算法复杂度分析：算法复杂度分析：算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。56例题一：排队买票问题n一一场场演演唱唱会会即即将将举举行行。现现有
36、有 n 个个歌歌迷迷排排队队买买票票，一一个个人人买买一一张张，而而售售票票处处规规定定，一一个个人人每每次次最最多多只只能能买买两两张张票票。假假设设第第 i 位位歌歌迷迷买买一一张张票票需需要要时时间间Ti（1in），队队伍伍中中相相邻邻的的两两位位歌歌迷迷（第第 j 个个人人和和第第 j+1 个个人人）也也可可以以由由其其中中一一个个人人买买两两张张票票，而而另另一一位位就就可可以以不不用用排排队队了了，则则这这两两位位歌歌迷迷买买两两张张票票的的时时间间变变为为 Rj，假假如如 RjTj+Tj+1，这这样样做做就就可可以以缩缩短短后后面面歌歌迷迷等等待待的的时时间间，加加快快整整个个售售票票的的进进程程。现现给给出出 n,Tj和和 Rj，求使每个人都买到票的最短时间和方法。求使每个人都买到票的最短时间和方法。57