[普及组]动态规划经典题目分析

动态规划经典题目分析中山纪念中学陈启峰一般步骤•确定状态：•状态的参数一般有•1）描述位置的：前(后)i单位，第i到第j单位，坐标为(i,j)等•2）描述数量的：取i个，不超过i个，至少i个等•3）描述对后有影响的：状态压缩的，一些特殊的性质一般步骤•转移方程：•1）检查参数是否足够；•2）分情况：最后一次操作的方式，取不取，怎么样放，前一项是什么•3）初始条件是什么。•4）注意无后效性。比如说，求A就要求Ｂ，求Ｂ就要求Ｃ，而求Ｃ就要求Ａ，这就不符合无后效性了。一般步骤•编程实现方式•1）递推•2）记忆化搜索（一般在状态的拓朴顺序不很明确时使用）一般步骤•恰当地使用数据可以使动态规划的时间复杂度降下。•队列——O(n^2*??)O(n*??)•线段树、堆、二叉查找树——O(n*??)O(logn*??)•Hash表、并查集——O(n*??)O(??)•此外运用四边行不等式可以使•O(n^3*??)O(n^2*??)经典题•最长公共子序列•最长上升子序列•最优二分检索树•最优矩阵链乘•最优三角剖分•任务调度问题叠放箱子•【问题】•某港口有一批箱子，将其编号，分别为1至N。每一个箱子的尺寸规格是一样的，现在要将其中某些箱子叠放起来，箱子叠放的规则如下：•一、每个箱子上最多只能直接叠放一个箱子；•二、编号较小的箱子不能放在编号较大的箱子之上；•三、每个箱子都给出了自身重量与可承受重量，每个箱子之上的所有箱子重量之和不得超过该箱的可承受重量。•为了节约堆放场地，希望你编程从中选出最多个箱子，使之能够在满足条件的情况下叠放起来。•【输入】•第一行是一个整数N（1≤N≤1000）。•以下共有N行，每行两个整数，中间以空格分隔，分别表示每个箱子的自身重量与可承受重量，两个数值均为小于等于3000的正整数。•【输出】•第一行应当输出最多可叠放的箱子总数M。【样例】有五个箱子，如下表：编号自身重量可承受重量119152713357468512则最多可以叠放4个箱子，方案之一如：1、2、3、5分析•设F[i,j]表示第i个箱子到第N个箱子中总重量为j的最大箱子数。•考虑第i个箱子放与不放的情况。•注意，能选的条件是•j≥weight[i]并且capacity≥j-weight[i]selectselectnot1]][,1[],1[max],[iweightjiFjiFjiF代码•programCQF_BOX;•usesmath;•constmaxn=1000;•varweight,capacity:array[1..maxn]oflongint;•f:array[1..maxn+1,0..6000]oflongint;•n:longint;•procedureinit;•vari:longint;•begin•readln(n);•fori:=1tondo•readln(weight[i],capacity[i]);•end;•procedurework;•vari,j,ans:longint;•begin•fillchar(f,sizeof(f),200);•f[n+1,0]:=0;•fori:=ndownto1do•forj:=0to6000dobegin•f[i,j]:=f[i+1,j];•if(j=weight[i])and(capacity[i]=j-weight[i])then•f[i,j]:=max(f[i,j],f[i+1,j-weight[i]]+1);•end;•ans:=0;•fori:=0to6000do•ans:=max(ans,f[1,i]);•writeln(ans);•end;CMI•给出一个1到n的排列，每次可以移动一个数到一个任意位置。问要达到状态1,2,3……n至少移动多少次？•SampleInput•5•21453•SampleOutput•2分析•答案就是N减去这个排列的最长上升子序列的长度lis。•为什么呢？证明•必要性：•一次移动就相当于删除一个数并添加上这个数。•删除一个数不会增加lis。•添加一个数最多使lis加1。•因此一次移动最多可以使lis加1•要达到目标状态至少要N-lis次移动。证明•充分性：•每次选取一个非lis上的一个数，并将它移动到lis上合适的位置。也就是说，将它移动到lis上前比它小，后比它大的位置。算法•运用动态规划：•F[i]表示以第i个数为结束的最长上升子序列的长度。•F[i]=max{F[j]+1|value[j]value[i]}•这是O(n^2)的•但是运用BST也可以让算法降到Ｏ(nlogn)•还有没有更好的方法呢？算法•建立一个数组last。•Last[i]表示长度为i的子序列中最小的最后一个数。•特别的last[0]=负无穷•假如现在已经处理了前i-1个数，考虑加入第i个数。算法•如果last[lis]value[i]，那么就•lis加上1，加后并令last[lis]为value[i]•否则找出最小k，使得last[k]≥value[i]•这时可以令last[k]为value[i]。因为value[i]可以添加到last[k-1]后（last[k-1]value[i])，而last[k]≥value[i]。代码•programCQF_CMI;•varvalue,last:array[0..200000]oflongint;•n:longint;•procedureinit;•vari,j:longint;•begin•readln(n);•fori:=1tondo•read(value[i]);•readln;•end;•procedurework;•varlis,i,j:longint;•begin•lis:=0;•last[lis]:=-maxlongint;•fori:=1tondo•ifvalue[i]last[lis]thenbegin•inc(lis);•last[lis]:=value[i];•end•else•update(0,lis);•writeln(n-lis);•end;•procedureupdate(a,b:longint);•begin•ifa=bthen•last[a]:=value[i]•else•iflast[(a+b)shr1]value[i]then•update(a,(a+b)shr1)•else•update((a+b)shr1+1,b);•end;寻宝游戏•游戏中的提示都由数列组成，而“藏宝图”则是一个N×M个数的表格。只要找出数列与表格的“接近程度”，就找到了当前位置与宝藏埋藏点的距离。“接近程度”的定义为：假设提示数列为{ai}，那么“藏宝图”中找出与其最为接近的数列{bi}(数列项数同为Len)，这两数列的接近程度就是数列与表格的接近程度，其中数列的接近程度D=∑(ai-bi)2(i∈[1,Len])，D越小就表示越接近。除此以外，数列{bi}还有以下的限制：用(xi,yi)表示数列{bi}中第i项在表格中的位置，则要求|xi-xi+1|+|yi-yi+1|=1(i∈[1,len-1]))，且同一位置可能在数列中出现多次。•为获得此大奖，你需要编写一个程序，求出表格和数列的接近程度。•序得出数列与表格的接近程度。寻宝游戏•SAMPLEINPUT•55•00010•10000•01000•00020•00000•6•101211•SAMPLEOUTPUT•3•数据范围•2≤N、M≤100，1≤Len≤250。表格和数列中的每一项都小于100。分析•设F[i,x,y]表示ai与表格中位于(x,y)的数向对应，且数列{ai}的前1～i-1项与表格中所有bi位置为(x,y)的数列的最小接近程度。•B1和B2~Bn是有点不一样的。•因为B2~Bn都和前面的数有位置关系，而B1没有。•所以初始化条件为•F[1,x,y]=(a[1]-table[x,y])2分析•转移方程•答案就是min{F[len,x,y]}]1,,1[],1,1[]1,,1[],1,1[min]),[][(],,[2yxiFyxiFyxiFyxiFyxtableiayxiF代码•programCQF_TREASURE;•usesmath;•vara:array[1..250]oflongint;•table:array[1..100,1..100]oflongint;•f:array[1..250,0..101,0..101]oflongint;•n,m,len:longint;•procedureinit;•vari,j:longint;•begin•readln(n,m);•fori:=1tondo•forj:=1tomdo•read(table[i,j]);•readln(len);•fori:=1tolendo•read(a[i]);•end;代码•procedurework;•vari,j,k,ans:longint;•begin•fillchar(f,sizeof(f),45);•fori:=1tondo•forj:=1tomdo•f[1,i,j]:=sqr(a[1]-table[i,j]);•fori:=2tolendo•forj:=1tondo•fork:=1tomdo•f[i,j,k]:=sqr(a[i]-table[j,k])+min(f[i-1,j-1,k],min(f[i-1,j,k-1],min(f[i-1,j+1,k],f[i-1,j,k+1])));•ans:=maxlongint;•fori:=1tondo•forj:=1tomdo•ans:=min(ans,f[len,i,j]);•writeln(ans);•end;数字游戏•小W发明了一个游戏，他在黑板上写出了一行数字a1，a2，a3，……，an，然后给你M个回合的机会，每会回你可以从中选择一个数字擦去它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合，所有你擦去的数字之和就是你所得的分数。•小W和他的好朋友小Y玩了这个游戏，可是他发现，对于每个给出的a和b序列，小Y的得分总比他高，所以他就很不服气。于是他想让你帮他算算，对于每个a和b序列，可以得到的最大得分是多少。数字游戏•输入文件：•输入文件的第一行是一个整数n（1=n=2000），表示数字个数；第二行一个整数m（1=m=n），表示回合数，接下来一行有n个不超过10000的正整数，a1，a2，a3，……，an表示原始序列，最后一行有n个不超过500的正整数，b1，b2，b3，……，bn，表示每回合每个数字递减的值。•输出文件：•输出文件只有一个整数，表示最大的可能得分。数字游戏•输入样例：•3•3•102030•456•输出样例：•47分析•我们知道，擦走的数字是有顺序的。如果可以规定一个序，删除的顺序必需和这个序相对应，就可以应用动态规划了。•假如a[i]在a[j]前删除，而b[i]小于b[j]的话，那么我们可以交换这两个数的删除顺序而使得总和更大。分析•所以，第一步就是对数按b[i]从大到小排序。排序后，删除的顺序就是从左到右的。•设F[i,j]表示从前i个删除j个数的最大分值。•F[i,j]=max{F[i-1,j],F[i-1,j-1]+a[i]-b[i]*(j-1)}代码•programCQF_GAME;•usesmath;•vara,b:array[1..2000]oflongint;•f:array[0..2000,0..2000]oflongint;•n,m:longint;•procedureinit;•vari:longint;•begin•readln(n);•readln(m);•fori:=1tondo•read(a[i]);•fori:=1tondo•read(b[i]);•end;•procedurework;•vari,j:longint;•proce