动态规划经典问题大合集


动态规划经典教程 引言:本人在做过一些题目后对 DP 有些感想,就写了这个总结: 第一节 动态规划基本概念 一,动态规划三要素:阶段,状态,决策。 他们的概念到处都是,我就不多说了,我只说说我对他们的理解: 如果把动态规划的求解过程看成一个工厂的生产线,阶段就是生产某个商品的不同的环节,状态就是 工件当前的形态,决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结,有一个个 的小结构成了最终的整个生产线。每个状态间又有关联(下一个状态是由上一个状态做了某个决策后产生 的)。 下面举个例子: 要生产一批雪糕,在这个过程中要分好多环节:购买牛奶,对牛奶提纯处理,放入工厂加工,加工后 的商品要包装,包装后就去销售……,这样每个环节就可以看做是一个阶段;产品在不同的时候有不同的 状态,刚开始时只是白白的牛奶,进入生产后做成了各种造型,从冷冻库拿出来后就变成雪糕(由液态变 成固态)。每个形态就是一个状态,那从液态变成固态经过了冰冻这一操作,这个操作就是一个决策。 一个状态经过一个决策变成了另外一个状态,这个过程就是状态转移,用来描述状态转移的方程就是 状态转移方程。 经过这个例子相信大家对动态规划有所了解了吧。 下面再说说我对动态规划的另外一个理解: 用图论知识理解动态规划:把动态规划中的状态抽象成一个点,在有直接关联的状态间连一条有向边, 状态转移的代价就是边上的权。这样就形成了一个有向无环图 AOE 网(为什么无环呢?往下看)。对这个 图进行拓扑排序,删除一个边后同时出现入度为 0 的状态在同一阶段。这样对图求最优路径就是动态规划 问题的求解。 二,动态规划的适用范围 动态规划用于解决多阶段决策最优化问题,但是不是所有的最优化问题都可以用动态规划解答呢? 一般在题目中出现求最优解的问题就要考虑动态规划了,但是否可以用还要满足两个条件: 最优子结构(最优化原理) 无后效性 最优化原理在下面的最短路径问题中有详细的解答; 什么是无后效性呢? 就是说在状态 i 求解时用到状态 j 而状态 j 求解又用到状态 k…..状态 N。 而求状态 N 时又用到了状态 i 这样求解状态的过程形成了环就没法用动态规划解答了,这也是上面用 图论理解动态规划中形成的图无环的原因。 也就是说当前状态是前面状态的完美总结,现在与过去无关。。。 当然,要是换一个划分状态或阶段的方法就满足无后效性了,这样的问题仍然可以用动态规划解。 三,动态规划解决问题的一般思路。 拿到多阶段决策最优化问题后,第一步要判断这个问题是否可以用动态规划解决,如果不能就要考虑 搜索或贪心了。当确定问题可以用动态规划后,就要用下面介绍的方法解决问题了: (1)模型匹配法: 最先考虑的就是这个方法了。挖掘问题的本质,如果发现问题是自己熟悉的某个基本的模型,就直接 套用,但要小心其中的一些小的变动,现在考题办都是基本模型的变形套用时要小心条件,三思而后行。 这些基本模型在后面的分类中将一一介绍。 (2)三要素法 仔细分析问题尝试着确定动态规划的三要素,不同问题的确定方向不同: 先确定阶段的问题:数塔问题,和走路问题(详见解题报告) 先确定状态的问题:大多数都是先确定状态的。 先确定决策的问题:背包问题。(详见解题报告) 一般都是先从比较明显的地方入手,至于怎么知道哪个明显就是经验问题了,多做题就会发现。 (3)寻找规律法: 这个方法很简单,耐心推几组数据后,看他们的规律,总结规律间的共性,有点贪心的意思。 (4)边界条件法 找到问题的边界条件,然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。 (5)放宽约束和增加约束 这个思想是在陈启锋的论文里看到的,具体内容就是给问题增加一些条件或删除一些条件使问题变的 清晰。 第二节 动态规划分类讨论 这里用状态维数对动态规划进行了分类: 1.状态是一维的 1.1 下降/非降子序列问题: 问题描述: {挖掘题目的本质,一但抽象成这样的描述就可以用这个方法解} 在一个无序的序列 a1,a2,a3,a4…an 里,找到一个最长的序列满足:ai<=aj<=ak…<=am,且 iaj>ak…>am,且 i>j>k…>m.(最长下降子序列)。 问题分析: 如果前 i-1 个数中用到 ak (ak>ai 或 ak<=ai)构成了一个最长的序列加上第 i 个数 ai 就是前 i 个数中用到 i 的最长的序列了。那么求用到 ak 构成的最长的序列有要求前 k-1 个数中…… 从上面的分析可以看出这样划分问题满足最优子结构,那满足无后效性么?显然对于第 i 个数时只考 虑前 i-1 个数,显然满足无后效性,可以用动态规划解。 分析到这里动态规划的三要素就不难得出了:如果按照序列编号划分阶段,设计一个状态 opt[i] 表示 前 i 个数中用到第 i 个数所构成的最优解。那么决策就是在前 i-1 个状态中找到最大的 opt[j]使得 aj>ai(或 aj<=ai),opt[j]+1 就是 opt[i]的值;用方程表示为:{我习惯了这种写法,但不是状态转移方程的标准写法 } opt[i]=max(opt[j])+1 (0<=jai) {最长下降子序列} 实现求解的部分代码: opt[0]:=maxsize;{maxsize 为 maxlongint 或-maxlongint} for i:=1 to n do for j:=0 to i-1 do if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then opt[i]:=opt[j]+1; ans:=-maxlongint; for i:=1 to n do if opt[i]>ans then ans:=opt[i]; {ans 为最终解} 复杂度:从上面的实现不难看出时间复杂度为 O(N2),空间复杂度 O(N); 例题 1 拦截导弹 (missile.pas/c/cpp) 来源:NOIP1999(提高组) 第一题 【问题描述】 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然 它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到 敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数),计算这套系统最多能拦 截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 【输入文件】missile.in 单独一行列出导弹依次飞来的高度。 【输出文件】missile.out 两行,分别是最多能拦截的导弹数,要拦截所有导弹最少要配备的系统数 【输入样例】 389 207 155 300 299 170 158 65 【输出样例】 6 2 【提交链接】 http://www.rqnoj.cn/Problem_217.html 【问题分析】 有经验的选手不难看出这是一个求最长非升子序列问题,显然标准算法是动态规划。 以导弹依次飞来的顺序为阶段,设计状态 opt[i]表示前 i 个导弹中拦截了导弹 i 可以拦截最多能拦截到 的导弹的个数。 状态转移方程: opt[i]=max(opt[j])+1 (h[i]>=h[j],0==a[i]) and (opt[j]+1>opt[i]) then opt[i]:=opt[j]+1; anslen:=0; for i:=1 to n do if opt[i]>anslen then anslen:=opt[i]; fillchar(opt,sizeof(opt),0); a[0]:=-maxlongint; for i:=1 to n do for j:=i-1 downto 0 do if (a[j]opt[i]) then opt[i]:=opt[j]+1; anstime:=0; for i:=1 to n do if opt[i]>anstime then anstime:=opt[i]; end; procedure print; begin writeln(anslen); writeln(anstime); close(input); close(output); end; begin init; main; print; end. 例题 2 合唱队形 (chorus.pas/c/cpp) 来源:NOIP2004(提高组) 第一题 N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的 K 位同学排成合唱队形。 合唱队形是指这样的一种队形:设 K 位同学从左到右依次编号为 1,2…,K,他们的身高分别为 T1, T2,…,TK, 则他们的身高满足 T1<...Ti+1>…>TK(1<=i<=K)。 你的任务是,已知所有 N 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱 队形。 【输入文件】 输入文件 chorus.in 的第一行是一个整数 N(2<=N<=100),表示同学的总数。第二行有 n 个整数, 用空格分隔,第 i 个整数 Ti(130<=Ti<=230)是第 i 位同学的身高(厘米)。 【输出文件】 输出文件 chorus.out 包括一行,这一行只包含一个整数,就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 【数据规模】 对于 50%的数据,保证有 n<=20; 对于全部的数据,保证有 n<=100。 【提交链接】 http://www.rqnoj.cn/Problem_26.html 【问题分析】 出列人数最少,也就是说留的人最多,也就是序列最长。 这样分析就是典型的最长下降子序列问题。只要枚举每一个人站中间时可以得到的最优解。显然它就 等于,包括他在内向左求最长上升子序列,向右求最长下降子序列。 我们看一下复杂度: 计算最长下降子序列的复杂度是 O(N2),一共求 N 次,总复杂度是 O(N3)。这样的复杂度对于这个 题的数据范围来说是可以 AC 的。但有没有更好的方法呢? 其实最长子序列只要一次就可以了。因为最长下降(上升)子序列不受中间人的影响。 只要用 OPT1 求一次最长上升子序列,OPT2 求一次最长下降子序列。这样答案就是 N-max(opt1[i]+opt2[i]-1). 复杂度由 O(N3)降到了 O(N2)。 【源代码】 program chorus; const fin='chorus.in'; fout='chorus.out'; maxn=200; var opt1,opt2,a:array[0..maxn] of longint; n,ans:longint; procedure init; var i:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); readln(n); for i:=1 to n do read(a[i]); end; procedure main; var i,j:longint; begin a[0]:=-maxlongint; for i:=1 to n do for j:=i-1 downto 0 do if (a[j]opt1[i]) then opt1[i]:=opt1[j]+1; a[n+1]:=-maxlongint; for i:=n downto 1 do for j:=i+1 to n+1 do if (a[j]opt2[i]) then opt2[i]:=opt2[j]+1; ans:=0; for i:=1 to n do if opt1[i]+opt2[i]>ans then ans:=opt1[i]+opt2[i]; end; procedure print; begin writeln(n-ans+1); close(input); close(output); end; begin init; main; print; end. 例题 3 Buy Low Buy Lower (buylow.pas/c/cpp) 来源: USACO 4-3-1 【问题描述】 “逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者,就要遵守这条秘诀: "逢低吸纳,越低越买" 这句话的意思是:每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的 次数越多越好,看看你最多能按这个规则买几次。 给定连续的 N 天中每天的股价。你可以在任何一天购买一次股票,但是购买时的股价一定要比你上次 购买时的股价低。写一个程序,求出最多能买几次股票。 以下面这个表为例, 某几天的股价是: 天数 1 2 3 4 5 6 7 8 9 10 11 12 股价 68 69 54 64 68 64 70 67 78 62 98 87 这个例子中,聪明的投资者(按上面的定义),如果每次买股票时的股价都比上一次买时低,那么他最 多能买 4 次股票。一种买法如下(可能有其他的买法): 天数 2 5 6 10 股价 69 68 64 62 【输入文件】buylow.in 第 1 行: N (1 <= N <= 5000),表示能买股票的天数。 第 2 行以下: N 个正整数 (可能分多行) ,第 i 个正整数表示第 i 天的股价. 这些正整数大小不会超过 longint(pascal)/long(c++). 【输出文件】buylow.out 只有一行,输出两个整数: 能够买进股票的天数,长度达到这个值的股票购买方案数量 在计算解的数量的时候,如果两个解所组成的字符串相同,那么这样的两个解被认为是相同的(只能 算做一个解)。因此,两个不同的购买方案可能产生同一个字符串,这样只能计算一次。 【输入样例】 12 68 69 54 64 68 64 70 67 78 62 98 87 【输出样例】 4 2 【提交链接】 http://www.rqnoj.cn/Problem_456.html 【问题分析】 从题目描述就可以看出这是最长下降子序列问题,于是求解第一问不是难事,以天数为阶段,设计状 态 opt[i] 表示前 i 天中要买第 i 天的股票所能得到的最大购买次数。 状态转移方程: opt[i]=max(opt[j])+1 (a[i]>=a[j],0=a[i],opt[j]=opt[i]-1) {sum 代表求和} 答案=sum(F(j)) {0a[i]) and (opt[j]+1>opt[i]) then opt[i]:=opt[j]+1; for i:=1 to n do begin j:=i-1; while (j>0) and ((opt[i]<>opt[j]) or (a[i]<>a[j])) do dec(j); next[i]:=j; end; F[0,1]:=1; for i:=1 to n+1 do for j:=i-1 downto next[i] do if (opt[j]=opt[i]-1) and (a[j]>a[i]) then Hinc(F[i],F[j]); end; procedure print; var i,top,m:longint; begin write(opt[n+1]-1,' '); top:=maxsize; while (top>1) and (F[n+1][top]=0) do dec(top); write(F[n+1,top]); for i:=top-1 downto 1 do begin m:=F[n+1,i]; while mD2 那么一定会相交,反之则不会相交。 当 C1>C2 时,如果 D1x do dec(j); if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end; until i>j; if j>L then quick(L,j); if iopt[i]) then opt[i]:=opt[j]+1; ans:=-maxlongint; for i:=1 to n do if ans0) do begin init; main; read(x,y); end; close(input); close(output); end. 1.2 背包问题 首先说说背包问题的基本模型: 现有 N 个物品,每个物品的价值为 V,重量为 W。求用一个载重量为 S 的背包装这些物品,使得所 装物品的总价值最高。 背包问题用贪心和搜索解,当然效果不佳,不过在我的贪心和搜索总结中会说到。显然标准的解法是 动态规化,我在解决这个问题时习惯设计一维状态,还可以设计二维的,二维状态在下面会讲,现在只讨 论用一维状态实现背包问题。 背包问题的分类: (1)小数背包:物品的重量是实数,如油,水等可以取 1.67 升…… (2)整数背包:<1>0/1 背包:每个物品只能选一次,或不选。不能只选一部分 <2>部分背包:所选物品可以是一部分。 (3)多重背包:背包不只一个。 小数背包:在贪心总结中会细讲。 整数背包: 部分背包:同小数背包。 0/1 背包:这个问题是最经常出现的问题,应该熟练掌握。 我们先看一下 0/1 背包的简化版: 现有 N 个物品,每个物品重量为 W,这些物品能否使在载重量为 S 的背包装满(即重量和正好为 S)? 如果不能那能使物品重量和最重达到多少? 针对这一问题我们以物品的个数分阶段,设计一个状态 opt[i]表示载重量为 i 的背包可否装满,显然 opt[i]的基类型是 boolean。 决策是什么呢? 当要装第 i 个物品时,如果前 i-1 个物品可以使载重为 k的背包装满,那么载重为 k+w[i]的背包就可 以装满。于是对于一个 opt[j]来说,只要 opt[j-w[i]]是 true(表示可装满)那 opt[j]就可以装满,但要注意: 针对每一个物品枚举背包的载重量时如果这样正向的推导会使同一个物品用好几次,因为 k+w[i]可装满那 k+w[i]+w[i]就可装满,但实际上是装不满的因为物品只有一个。解决这个问题很简单,只要逆向推导就 OK 了。 这样划分阶段,设计状态,满足无后效性么? 显然对于物品只有一个每一个阶段都是独立的,物品的顺序并不影响求解,因为装物品的次序不限。 而对于 opt[j]只考虑 opt[j-w[i]]而不考虑后面的,所以满足无后效性。 有了上面的分析不难写出状态转移方程: opt[j]:=opt[j-w[i]] {opt[j-w[i]]=true} 时间复杂度: 阶段数 O(S)*状态数(O(N))*转移代价(O(1))=O(SN) 下面看几个例题: 例题 5 装箱问题 (pack.pas/c/cpp) 来源:NOIP2001(普及组) 第四题 【问题描述】 有一个箱子容量为 V(正整数,0<=V<=20000),同时有 n 个物品(0<=n<=30),每个物品有一个体积 (正整数)。 要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。 【输入文件】 第一行,一个正整数 V 表示箱子的容量,第二行,一个正整数 N 表示物品个数,接下来 N 行列出这 N 个物品各自的体积。 【输出文件】 单独一行,表示箱子最小的剩余空间。 【输入样例】 24 6 8 3 12 7 9 7 【输出样例】 0 【提交链接】 http://www.rqnoj.cn/Problem_147.html 【问题分析】 本题是经典的 0/1 背包问题,并且是 0/1 背包的简化版,把箱子看做背包,容量看做载重量,体积看 做重量,剩余空间最小也就是尽量装满背包。于是这个问题便成了: 有一个栽重量为 V 的背包,有 N 个物品,尽量多装物品,使背包尽量的重。 设计一个状态 opt[i]表示重量 i 可否构成。 状态转移方程:opt[j]:=opt[j-w[i]] {opt[j-w[i]]=true} 最终的解就是 v-x(x<=n 且 opt[x]=true 且 opt[x+1..n]=false)。 【源代码 1】 program pack; const fin='pack.in'; fout='pack.out'; maxv=20010; maxn=100; var opt:array[0..maxv] of boolean; w:array[0..maxn] of longint; v,n,x:longint; procedure init; var i:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(v); read(n); for i:=1 to n do read(w[i]); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),false); opt[0]:=true; for i:=1 to n do for j:=v downto w[i] do if opt[j-w[i]] then opt[j] :=true; x:=v; while not opt[x] do dec(x); end; procedure print; begin writeln(v-x); close(input); close(output); end; begin init; main; print; end. 例题 6 砝码称重 来源:NOIP1996(提高组) 第四题 【问题描述】 设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚(其总重<=1000),用他们能称出的重量的种类数。 【输入文件】 a1 a2 a3 a4 a5 a6 (表示 1g 砝码有 a1 个,2g 砝码有 a2 个,…,20g 砝码有 a6 个,中间有空格)。 【输出文件】 Total=N (N 表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)。 【输入样例】 1 1 0 0 0 0 【输出样例】 TOTAL=3 【问题分析】 把问题稍做一个改动,已知 a1+a2+a3+a4+a5+a6 个砝码的重量 w[i],w[i]∈{1,2,3,5,10,20} 其中砝码重 量可以相等,求用这些砝码可称出的不同重量的个数。 这样一改就是经典的 0/1 背包问题的简化版了,求解方法完全和上面说的一样,这里就不多说了,只 是要注意这个题目不是求最大载重量,是统计所有的可称出的重量的个数。 【源代码 1】 program P4; const maxn=1010; w:array[1..6] of longint=(1,2,3,5,10,20); var opt:array[0..maxn] of boolean; a:array[1..6] of longint; procedure init; var i:longint; begin for i:=1 to 6 do read(a[i]); end; procedure main; var i,j,k:longint; begin fillchar(opt,sizeof(opt),false); opt[0]:=true; for i:=1 to 6 do for j:=1 to a[i] do for k:=maxn downto w[i] do if opt[k-w[i]] then opt[k]:=true; end; procedure print; var ans,i:longint; begin ans:=0; for i:=1 to maxn do if opt[i] then inc(ans); writeln(ans); end; begin init; main; print; end. 例题 7 积木城堡 来源:vijos P1059 【问题描述】 XC 的儿子小 XC 最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的,城堡的 每一层是一块积木。小 XC 是一个比他爸爸 XC 还聪明的孩子,他发现垒城堡的时候,如果下面的积木比 上面的积木大,那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。 小 XC 想把自己垒的城堡送给幼儿园里漂亮的女孩子们,这样可以增加他的好感度。为了公平起见, 他决定送给每个女孩子一样高的城堡,这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他 发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了, 他灵机一动,想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木,使得最终每座城堡都一 样高。为了使他的城堡更雄伟,他觉得应该使最后的城堡都尽可能的高。 任务: 请你帮助小 XC 编一个程序,根据他垒的所有城堡的信息,决定应该移去哪些积木才能获得最佳的效 果。 【输入文件】 第一行是一个整数 N(N<=100),表示一共有几座城堡。以下 N 行,每行是一系列非负整数,用一个空 格分隔,按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1 结束。一座城堡中的积木不超过 100 块,每块积木的棱长不超过 100。 【输出文件】 一个整数,表示最后城堡的最大可能的高度。如果找不到合适的方案,则输出 0。 【输入样例】 2 2 1 -1 3 2 1 -1 【输出样例】 3 【提交链接】 http://www.vijos.cn/Problem_Show.asp?id=1059 【问题分析】 首先要说明一点,可以挪走任意一个积木,不见得是最上面的。 初看题目有点茫然,但抽象一下就。。。。。。。。。。 其实塔好积木再拿走,就相当于当初搭的时候没选拿走的积木。这样一转化思维,问题就清楚了。把 积木可搭建的最大高度看做背包的载重,每块积木的高度就是物品的重量。也就是用给定的物品装指定的 包,使每个包装的物品一样多,且在符合条件的前提下尽量多。 这样就变成经典的背包问题了。 对于每一个城堡求一次,最终找到每一个城堡都可达到的最大高度即可。 【源代码 1】 const maxhig=7000; maxn=100; var n,top:longint; opt:array[0..maxn,0..maxhig] of boolean; a:array[0..maxn] of longint; procedure init; var i:longint; begin readln(n); fillchar(opt,sizeof(opt),false); for i:=1 to n do opt[i,0]:=true; end; function can(m:longint):boolean; var i:longint; begin can:=true; for i:=1 to n do if not opt[i,m] then exit(false); end; procedure main; var ii,m,tothig,i,j,ans:longint; begin for ii:=1 to n do begin top:=0; read(m); tothig:=0; while m>0 do begin inc(top); a[top]:=m; inc(tothig,m); read(m); end; for i:=1 to top do for j:=tothig downto 1 do if (j-a[i]>=0) and (opt[ii,j-a[i]]) then opt[ii,j]:=true; end; ans:=maxhig; while not opt[1,ans] do dec(ans); while not can(ans) do dec(ans); writeln(ans); end; begin init; main; end. 回顾上面的内容充分说明动态规划的本质就是递推。其实按照我的理解(动规涉及最优决策,递推是 单纯的总结)背包问题的简化版更准确点算是递推而非动态规划,至于动归和递推之间的界线本来就很模 糊(至少我这么认为)把它看做什么都可以,没必要咬文嚼字。 回到 0/1 背包的原问题上(如果你忘了就去上面看看)。 如果在不知道这个模型的情况下我们怎么做这个题呢? 这就要用到第一节提到的方法二:三要素法。 题目中明确说明对于一个物品要不就拿走要不就放下,其实题目赤裸裸的告诉我们决策就是不拿(用 0 表示)或拿(用 1 表示)。这样想都不用想就知道了决策,这也是本题的突破口。知道了决策写个搜索的 程序应该是很轻松的了。 那么阶段是什么呢? 显然,给你一堆东西让你往包里塞,你当然是一个一个的拿来,塞进去。那么阶段很明显就是物品的 个数。 状态又是什么呢? 有的人在装东西时有个习惯(比如说我)就是先把东西分类,然后把同类的东西打个小包,最后再把 小包放进去,我们可以按这个思想给物品打一些小包,也就是按照单位为 1 的递增的顺序准备好多个小包, 比如载重是 6 的包,可以为它准备载重是 1,2,3,4,5 的小包。这样状态就可以想出来了: 设计状态 opt[i,j]表示装第 i 个物品时载重为 j 的包可以装到的最大价值。 opt[i-1,j] (j-w[i]<0,i>0) 状态转移方程:opt[i,j]=max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]} (j-w[i]>=0,i>0) (w[i]:第 i 个物品的重量,v[i]第 i 个物品的价值) 解释:要载重为 j 的背包空出 w[i](j-w[i])的空间且装上第 i 个物品,比不装获得的价值大就装上它。 边界条件:opt[0,i]=0; (i∈{1..S}) 注: 这种二维的状态表示应该在下节讲,但是为了方便理解先在这里说了。 上面的方法动态规划三要素都很明显,实现也很简单。但是在我初学背包时却用另外一种一维的状态 表示法。 用第一节说的思考方法五(放宽约束和增加约束)再重新思考一下这个问题: 怎么放宽约束呢? 把题目中的价值去掉,不考虑价值即最优就变成背包问题的简化版了。那简化版的求解对我们有何启 示呢? 再一次增加约束:背包只能装满。 显然对于 N 个装满背包的方案中只要找到一个价值最大的就是问题的解。那么装不满怎么办呢?其实 装不满背包,它总要达到一定的重量(X)。我们可以把这种情况看作是装满一个载重为 X 的小包。 总结一下上面的思维过程: 放宽约束让我们找到问题的突破口——和背包问题简化版一样,我们可以确定载重为 S 的背包是否可 以装满。 增加约束让我们找到问题的求解方法——在装满背包的方案中选择最优的一个方案。 这样问题就解决了。 设计一个状态 opt[j]表示装满载重为 j 的背包可获得的最大价值。对于第 i 个物品,只要 opt[j-w[i]]可 以装满且 opt[j-w[i]]+v[i]比 opt[j]大就装上这个物品(更新 opt[j])。 怎么使 opt[j]既有是否构成又有最优的概念呢? opt[j]只表示最优,只不过使初始条件+1,判断 opt[j]是否为 0,如果 opt[j]=0 说明 j 装不满。 边界条件:opt[0]=1; 状态转移方程:opt[j]=max{opt[j-w[i]]} (0y then max:=x else max:=y; end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); for i:=1 to n do for j:=1 to t do if j-w[i]<0 then opt[i,j]:=opt[i-1,j] else opt[i,j]:=max(opt[i-1,j],opt[i-1,j-w [i]]+v[i]); end; procedure print; begin writeln(opt[n,t]); close(output); end; begin init; main; print; end. 【源代码 2】 {一维状态} program medic; const fin='medic.in'; fout='medic.out'; maxt=1010; maxn=110; var opt:array[0..maxt] of longint; w,v:array[0..maxn] of longint; ans,t,n:longint; procedure init; var i:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); readln(t,n); for i:=1 to n do read(w[i],v[i]); close(input); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); opt[0]:=1; for i:=1 to n do for j:=t downto w[i] do if (opt[j-w[i]]>0) and (opt[j-w[i]]+v[i]>opt[j]) then opt[j]:=opt[j-w[i]]+v[i]; ans:=-maxlongint; for i:=1 to t do if opt[i]>ans then ans:=opt[i]; end; procedure print; begin writeln(ans-1); close(output); end; begin init; main; print; end. 例题 9 开心的金明 来源:NOIP2006(普及组)第二题 【问题描述】 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他 高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N 元钱就 行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的 N 元。于是,他把 每件物品规定了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上查到了每件 物品的价格(都是整数元)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重 要度的乘积的总和最大。设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1...jk, 则所求的总和为:v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入的第 1 行,为两个正整数,用一个空格隔开: N m (其中 N(<30000)表示总钱数,m(<25)为希望购买物品的个数。) 从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 2 个非负整数 v p (其中 v 表示该物品的价格(v≤10000),p 表示该物品的重要度(1~5)) 【输出文件】 输出只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000) 【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 3900 【提交链接】 http://www.rqnoj.cn/Problem_2.html 【问题分析】 这仍然是一道典型的 0/1 背包,只不过注意这个问题中的价值对应背包模型中的重量,这个问题中的 价值和重要度的乘积是背包模型中的价值。(很饶口啊)。 具体实现同背包模型一样,这里不多说了。 【源代码】 program p2; const maxn=30010; maxm=30; var opt:array[0..maxn] of longint; v,p:array[0..maxm] of longint; n,m:longint; procedure init; var i:longint; begin readln(n,m); for i:=1 to m do readln(v[i],p[i]); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); opt[0]:=1; for i:=1 to m do begin for j:=n downto 1 do begin if (j-v[i]>=0) and (opt[j-v[i]]>0) and (opt[j-v[i]]+v[i]*p[i]>opt[j])then opt[j]:=opt[j-v[i]]+v[i]*p[i]; end; end; end; procedure print; var i,ans:longint; begin ans:=0; for i:=1 to n do if opt[i]>ans then ans:=opt[i]; writeln(ans-1); end; begin init; main; print; end. 例题 10 金明的预算方案 (budget.pas/c/cpp) 来源:NOIP2006 第二题 【问题描述】 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让 他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N 元钱 就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主 件的,下表就是一些主件与附件的例子: 主件 附件 电脑 打印机,扫描仪 书柜 图书 书桌 台灯,文具 工作椅 无 如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。 附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 N 元。于是,他把每件物品 规定了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格 (都是 10 元的整数倍)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度 的乘积的总和最大。 设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1,j2,……,jk,则所 求的总和为: v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号) 请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入文件 budget.in 的第 1 行,为两个正整数,用一个空格隔开:N m (其中 N(<32000)表示总钱数,m(<60)为希望购买物品的个数。) 从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 3 个非负整数: v p q (其中 v 表示该物品的价格(v<10000),p 表示该物品的重要度(1~5),q 表示该物品是主件还是附 件。如果 q=0,表示该物品为主件,如果 q>0,表示该物品为附件,q 是所属主件的编号) 【输出文件】 输出文件 budget.out 只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 (<200000)。 【输入样例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200 【提交链接】 http://www.rqnoj.cn/Problem_6.html 【问题分析】 这道题是一道典型的背包问题,比较麻烦的就是它还存在附件和主件之分。但这并不影响解题,由于 附件最多两个,那么我们对主、附件做一个捆绑就行了。 (1)标准算法 因为这道题是典型的背包问题,显然标准算法就是动态规划。由于我们要对主、附件做捆绑,由于题 目没有直接给出每个主件对应的附件,所以还需要做一个预处理:另开两个数组 q1,q2 来分别记录对应 的第 i 个主件的附件。那么对于附件不需要处理。而主件的花费就有 4 种情况了。( 下面用 W 表示花费) W1=v[i] (只买主件) W2=v[i]+v[q1[i]] (买主件和第一个附件) W3=v[i]+v[q2[i]] (买主件和第二个附件) W4=v[i]+v[q1[i]]+v[q2[i]] (买主件和那两个附件) 设计一个状态 opt[i]表示花 i 元钱可买到的物品的价格个重要度最大值。边界条件是 opt[0]=0 但是为了 区分花 i 元钱是否可买到物品我们把初始条件 opt[0]:=1;这样 opt[i]>0 说明花 i 元可以买到物品。这样就不 难设计出这个状态的转移方程来: opt[i]=max{opt[i],opt[i-wj]} ((i-wj>0) and (opt[i-wj]>0)) (0y then exit(x); exit(y); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); opt[0]:=1; for j:=1 to m do for i:=n downto v[j] do if q[j]=0 then begin if (i-v[j]>=0) and (opt[i-v[j]]>0) then opt[i]:=max(opt[i],opt[i-v[j]] +v[j]*p[j]); if (i-v[j]-v[q1[j]]>=0) and (opt[i-v[j]-v[q1[j]]]>0) then opt[i]:=max(opt[i],opt[i-v[j]- v[q1[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[ j]]); if (i-v[j]-v[q2[j]]>=0) and (opt[i-v[j]-v[q2[j]]]>0) then opt[i]:=max(opt[i],opt[i-v[j]- v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[ j]]); if (i-v[j]-v[q1[j]]-v[q2[j]]>=0) and (opt[i-v[j]-v[q1[j]]-v[q2[j]]]>0) then opt[i]:=max(opt[i],opt[i-v[j]- v[q1[j]]-v[q2[j]]]+v[j]*p[j]+v[q1[j ]]*p[q1[j]]+v[q2[j]]*p[q2[j]]); ans:=max(ans,opt[i]); end; end; procedure print; begin writeln((ans-1)*10); close(output); end; begin init; main; print; end. 上面提到的几个例题都是最基础的题目,而且把问题抽象后就与背包问题的基本模型一样了,但有些 题目用到了基本模型,要求的解却不一定跟模型一样,下面看个例子: 例题 11 Money Systems (money.pas/c/cpp) 来源:USACO 2.3 【问题描述】 母牛们不但创建了他们自己的政府而且建立了自己的货币系统。[In their own rebellious way],他们对 货币的数值感到好奇。 传统地,一个货币系统是由 1,5,10,20 或 25,50, 和 100 的单位面值组成的。 母牛想知道有多少种不同的方法用货币系统中的货币来构造一个确定的数值。 举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18 单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会 适合 long long (C/C++) 和 Int64 (Free Pascal)。 【输入文件】 货币系统中货币的种类数目是 V (1<= V<=25)。要构造的数量钱是 N (1<= N<=10,000)。 第 1 行:二整数,V 和 N 第 2 行:可用的货币 V 个整数。 【输出文件】 单独的一行包含那个可能的构造的方案数。 【输入样例】 3 10 1 2 5 【输出样例】 10 【问题分析】 把钱面值,要构造的钱看做载重为 N 的背包,这个问题便是 0/1 背包的简化版了,但这个问题和传统 模型有所差异,不是判断 N 是否可构成,而是求构成 N 的方案,而且这里的面值是可以重复利用的(你 可以看做是物品有无限多)。 对于第一个问题,只要把原来 BOOLEAN 型的状态改为 INT64,在递推过程中累加方案数即可。 对于第二个问题,基本模型中为了避免重复在内重循环枚举背包载重时采用倒循环,现在只要正向循 环就 OK 了。 复杂度与原模型相同。 【源代码】 { ID:hhzhaojia2 PROG:money LANG:PASCAL } program money; const fin='money.in'; fout='money.out'; maxv=100; maxn=10010; var a:array[0..maxv] of longint; opt:array[0..maxn] of int64; v,n:longint; procedure init; var i:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(v,n); for i:= 1 to v do read(a[i]); close(input); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); opt[0]:=1; for i:=1 to v do for j:=a[i] to n do inc(opt[j],opt[j-a[i]]); end; procedure print; begin writeln(opt[n]); close(output); end; begin init; main; print; end. 背包问题方案的求法: 和大多数 DP 问题的方案的求法一样,增加一个数组 path 和状态维数相同用来记录当前状态的决策就 OK 了。 输出方案时候通过当前决策推出上一决策,这一连串的决策序列就是要求的方案。 下面看这样一个数据: 载重:6 物品个数:3 重量 价值 物品 1:3 10 物品 2:2 2 物品 3:1 9 一维状态求解过程: i=1:(枚举物品) opt[0..6]= 1 0 0 11 0 0 0 path[0..6]=0 0 0 1 0 0 0 {记录最后装入包中的物品的编号} i=2 opt[0..6]=1 0 3 11 0 13 0 path[0..6]=0 0 2 1 0 2 0 i=3 opt[0..6]=1 10 3 12 20 13 22 path[0..6]=0 3 2 3 3 2 3 二维状态求解过程: (略) 可以看到一维状态的最优解是正确的,但细心分析发现一个惊人的问题:方案不对! 什么最优解正确而方案不正确呢? 因为在解 i=3 时 opt[6]用到的方案数应该是 9+2+10=21。显然这个方案是正确的,所以最优解正确。 但是求解完 opt[6]后,接着求解 opt[3]却把原来的 opt[3]=10 改成了 opt[3]=2+9=11 这样,在整个求解过程 结束后最后的方案 opt[6]=9+2+10 就变成了 opt[6]=9+2+2+9 也就是说 1,2 两个物品装了两次。 这也正是我要说的下面的问题; 背包问题一维状态于二维状态的优劣: 显然,一维状态的维数少空间复杂度低。甚至在一些问题上可以减轻思考负担。既然这样是不是我们 就应该屏弃二维状态解法呢? 由于一维状态在求解方案时存在错误,所以二维状态还是很有用啊。当然有些问题虽然也是在求解方 案但要求方案唯一这样就又可以用一维状态了。 看到这里觉得头晕就上趟厕所,返回来看下面的例题: 例题 12 新年趣事之打牌 来源: vijos P1071 【问题描述】 过年的时候,大人们最喜欢的活动,就是打牌了。xiaomengxian 不会打牌,只好坐在一边看着。 这天,正当一群人打牌打得起劲的时候,突然有人喊道:“这副牌少了几张!”众人一数,果然是少了。 于是这副牌的主人得意地说:“这是一幅特制的牌,我知道整副牌每一张的重量。只要我们称一下剩下的 牌的总重量,就能知道少了哪些牌了。”大家都觉得这个办法不错,于是称出剩下的牌的总重量,开始计 算少了哪些牌。由于数据量比较大,过了不久,大家都算得头晕了。 这时,xiaomengxian 大声说:“你们看我的吧!”于是他拿出笔记本电脑,编出了一个程序,很快就把 缺少的牌找了出来。 如果是你遇到了这样的情况呢?你能办到同样的事情吗? 【输入文件】 第一行一个整数 TotalW,表示剩下的牌的总重量。 第二行一个整数 N(10 then begin if opt[j]=0 then path[j]:=i; {只有当前 状态没求过才记录方案} inc(opt[j],opt[j-w[i]]); end; if opt[total]=0 then begin writeln('0'); halt; end; if opt[total]>1 then begin writeln('-1'); halt; end; i:=total; while i>0 do begin ans[path[i]]:=false; i:=i-w[path[i]]; end; end; procedure print; var i:longint; begin for i:=1 to n do if ans[i] then write(i,' '); end; begin init; main; print; end. 1.3 其它问题 一维动态规划最常见的就是前面总结的最长下降/非降子序列和 0/1 背包问题了,当然还有别的一些题。 由于不是很常见所以没有固定的解题模式,到时候具体问题具体分析。下面再看一个例子: 例题 13 挖地雷问题 (P3.pas/c/cpp) 来源:NOIP1996(提高组)第三题(有改动) 【问题描述】 在一个地图上有 N 个地窖(N<=20),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接 路径。 当地窖及其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅 能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使某人能挖到最多的地雷。 【输入文件】 N: (表示地窖的个数) W1,W2,W3,……WN (表示每个地窖中埋藏的地雷数量) A12…………………A1N (aij=1 表示第 i 个地窖与第 j 个地窖有连接,=0 表示无连接) A23…………A2N …… AN-1 AN 【输出文件】 K1--K2--……--KV (挖地雷的顺序) MAX (挖地雷的数量) 【输入样例】 5 10 8 4 7 6 1 1 1 0 0 0 0 1 1 1 【输出样例】 1 -> 3 -> 4 -> 5 max=27 【Hint】 题目中的路径是有向的且无环路(这是我做的改动,原题中没有要求)。 【问题分析】 看到题目的第一印象是贪心——以一点出发找与他连接的地窖中地雷数最多的一个。 但很容易想到反例: 5 1 2 1 1 100 1 1 0 0 0 1 0 0 1 0 按照贪心答案是 4,但实际上答案是 102。 于是就不得不放弃贪心的想法。 但是贪心给了我们启示:从一个顶点出发要选择向一个与他相连且以该点出发可以挖到较多雷的点 走。(有点拗口) 另一种解释:如果一个顶点连同 N 个分量,显然选择一个较大的就是问题的解答,这个定义是满足最 优化原理的。 那它满足无后效性么? 因为图是有向的,所以以与该顶点相连的点在往下走的路线中不包括该点。也就是说图是一个 AOV 网(有向无环图)。 既然满足最优化原理,且无后效性,我们就可以用动态规划解了。 这个问题的阶段就是拓扑序列,但由于输入是倒三角形,所以我们没必要求拓扑序列,只要从 N 倒着 求解就可以了。 设计状态 opt[i]表示以 i 点出发可以挖到最多的雷的个数。 状态转移方程:opt[i]=max{opt[ j ]}+w[i] (g[i,j]=1) (g 存图,w[i]存第 i 个地窖中的雷的个数)。 时间复杂度: 状态数 O(n)*转移代价 O(n)=O(n2) 这个题目还要求出路径,可以用一个辅助数组 path 来记录,path[i]表示从第 i 个出发走到的下一个点 的编号。求解完只要按 path 记录的路径输出即可。 【源代码】 program P3; const fin='P3.in'; fout='P3.out'; maxn=200; var g:array[0..maxn,0..maxn] of longint; n,ans:longint; w,opt,path:array[0..maxn] of longint; procedure init; var i,j:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(n); fillchar(g,sizeof(g),0); for i:=1 to n do read(w[i]); for i:=1 to n do for j:=i+1 to n do read(g[i,j]); close(input); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); fillchar(path,sizeof(path),0); for i:=n downto 1 do begin for j:=i+1 to n do if (g[i,j]=1) and (opt[j]>opt[i]) then begin opt[i]:=opt[j]; path[i]:=j; end; inc(opt[i],w[i]); end; ans:=1; for i:=2 to n do if opt[i]>opt[ans] then ans:=i; end; procedure print; var i:longint; begin write(ans); i:=path[ans]; while i>0 do begin write('-->',i); i:=path[i]; end; writeln; writeln('max=',opt[ans]); close(output); end; begin init; main; print; end. 2.状态是二维的 通过前面的学习,我想应该对动态规划不陌生了,我学习动态规划是没这么系统,二维,一维一起上。 二维状态的动态规划是重中之重。 所谓二维状态就是说一般设计的状态是 opt[i,j]形式的。那 i,j 可以代表什么呢? 有很多朋友问过我这个问题,我的回答是: (1)i,j 组合起来代表一个点的坐标(显然是平面坐标系)(如:街道问题)。 (2)i,j 组合表示一个矩阵的单元的位置(第 i 行,第 j 列)(如:数塔问题) (3)起点为 i 长度为 j 的区间。(如:回文词) (4)起点为 i 终点为 j 的区间。(如:石子合并问题) (5)两个没关联的事物,事物 1 的第 i 个位置,对应事物 2 的第 j 个位置(花店橱窗设计) (6)两个序列,第一个序列的前 i 个位置或第 i 个位置对应第 2 个序列的第 j 个位置或前 j 个位置。(最 长公共子序列)。 (7)其它 下面通过例题和基本模型进一步说明: 2.1 数塔问题 数塔问题来源于一道经典的 IOI 的题目,直接说题,通过题目总结共性。以后遇到类似的题目可以参 照这个模型。 例题 14 数塔问题 (numtri.pas/c/cpp) 来源:IOI94 【问题描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大(小)。每一步可以走 到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的样例中,从 7 到 3 到 8 到 7 到 5 的路径产生了最大和:30 【输入文件】 第一个行包含 R(1<= R<=1000) ,表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 所有被供应的整数是非负的且不大于 100。 【输出文件】 单独的一行包含那个可能得到的最大的和。 【输入样例】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 【输出样例】 30 【提交链接】 http://poj.org/problem?id=1163 【问题分析】 这个问题是学习动态规划最简单最经典的问题,说它经典是因为它的阶段、状态、决策都十分明显。 刚看到题目觉得没有入手点,连怎么储存,描述这个金字塔都是问题,看输入样例发现:数字金字塔 可以变成像输入样例那样的下三角,这样可以用一个二维数组 a 储存它,并且可以用(i,j)描述一个数字 在金字塔中的位置。 对于中间的一个点来说,想经过它则必须经过它的上方或左上(针对变化后的三角形)。也就是说经 过这个点的数字和最大等于经过上方或左上方所得的“最大和”中一个更大的加上这个点中的数字。显然 这个定义满足最优子结构。 这样阶段很明显就是金字塔的层,设计一个二维状态 opt[i,j]表示走到第 i 行第 j 列时经过的数字的最 大和。决策就是 opt[i-1,j] 或 opt[i-1,j-1]中一个更大的加上(i,j)点的数字。 对于一个点只考虑上面或左上即前一阶段,满足无后效性。 状态转移方程(顺推): opt[i-1,j]+a[i,j] (j=1) opt[i,j]= opt[i-1,j-1]+ a[i,j] (j=i) max{opt[i-1,j],opt[i-1,j-1]}+ a[i,j] (1=0 所以方程也可以这样写: opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j] 同理 j=i 时方程也可以写成上面那样,所以方程综合为: opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j](0opt[i+1,j+1] then opt[i,j]:=opt[i+1,j]+a[i,j] else opt[i,j]:=opt[i+1,j+1]+a[i,j]; end; procedure print; begin writeln(opt[1,1]); close(output); end; begin init; main; print; end. 例题 15 Henry 捡钱 (money.pas/c/cpp) 来源:Dream Team 邀请赛 【问题描述】 最近,Henry 由于失恋(被某大牛甩掉!)心情很是郁闷。所以,他去了大牛家,寻求 Michael 大牛的帮 助,让他尽快从失恋的痛苦中解脱出来。Michael 大牛知道 Henry 是很爱钱的,所以他是费尽脑水,绞尽 脑汁想出了一个有趣的游戏,帮助 Henry…. Michael 感觉自己简直是个天才(我们从不这么认为),就把这个游戏取名为:Henry 拣钱。为了帮助 更多的人采用这种方法早日脱离失恋之苦,Michael 特地选在这次 DT 比赛中把游戏介绍给大家….(大家 鼓掌!!!) 其实,这个游戏相当垃圾,目的就是为了满足 Henry 这种具有强烈好钱心理的人。游戏是这样的: Michael 首先找到了一块方形的土地,面积为 m*n(米^2)。然后他将土地划分为一平方米大小的方形小格。 Michael 在每个格子下都埋有钱(用非负数 s 表示,表示人民币的价值为 s)和炸弹(用负数 s 表示,表示 Henry 挖出该方格下的东西会花掉 s 的钱去看病,医炸弹炸伤的伤口)…。游戏的要求就是让 Henry 从一 侧的中间列出发,按照下图的 5 种方式前进(前进最大宽度为 5),不能越出方格。他每到一个格子,必定 要取走其下相应的东西。直到到达土地的另一侧,游戏结束。不用说也知道,Henry 肯定想得到最多的人 民币。所以他偷窥了 Michael 埋钱的全过程,绘成了一张距阵图。由于他自己手动找会很麻烦,于是他就 找到了学习编程的你。请给帮他找出,最大人民币价值。 拣钱路线规则(只有 5 个方向,如下图): H 为 Henry 的出发点,每组数据的出发点都是最后一行的中间位置! (前方 5 个格子为当前可以到达的) 【输入文件】 第一行为 m n.(n 为奇数),入口点在最后一行的中间。 接下来为 m*n 的数字距阵。 共有 m 行,每行 n 个数字,数字间用空格隔开,代表该格子下是钱或炸弹。 为了方便 Henry 清算,数字全是整数。 【输出文件】 一个数,为你所找出的最大人民币价值。 【输入样例】 6 7 16 4 3 12 6 0 3 4 -5 6 7 0 0 2 6 0 -1 -2 3 6 8 5 3 4 0 0 -2 7 -1 7 4 0 7 -5 6 0 -1 3 4 12 4 2 【输出样例】 51 【数据范围】 N and M<=200。 结果都在 longint 范围内。 【问题分析】 去掉题目华丽的伪装,我们可以这样描述这个题目: 给定一个数字矩阵,从最后一层的中间出发可以向图上所示的 5 个方向走,直到走到第一层,使经过 的数字和最大。 如果我们不考虑负数对问题的影响,这个问题的描述就是经典的数塔问题了,只不过将塔变成了矩阵。 这样就可以用刚刚讲过的数塔问题的模型解这个题目了,我就不多说了。 状态转移方程: opt[i,j]=max{opt[i-1,k]}+a[i,j] (j-2<=k<=j+2) 【源代码】 program money; const fin='money.in'; fout='money.out'; maxn=210; var a,opt:array[0..maxn,0..maxn] of longint; n,m,ans,max:longint; procedure init; var i,j:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); readln(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); end; procedure main; var i,j,k:longint; begin for i:=1 to n do for j:=1 to m do begin max:=-maxlongint; for k:=j-2 to j+2 do if (k>0) and (k<=m) and (opt[i-1,k]>max) then max:=opt[i-1,k]; opt[i,j]:=max+a[i,j]; end; ans:=-maxlongint; i:=(1+m) div 2; for j:=i-2 to i+2 do if (j>0) and (j<=m) and (opt[n,j]>ans) then ans:=opt[n,j]; end; procedure print; begin writeln(ans); close(input); close(output); end; begin init; main; print; end. 2.2 街道问题 和数塔问题一样街道问题也来源于一道典型的例题,下面我们看一下这道题。 例题 16 街道问题 (way.pas/c/cpp) 来源:《奥赛经典》(提高篇) 【问题描述】 如图所示的矩形图中找到一条从左下角到右上角的最短路径,图中数字表示边的长度。只能向右或向 上走。 【输入文件】第一行两个数,N M,矩形的点有 N 行 M 列。(0,则另一序列 Z= < z1, z2,…, zk>是 X 的子序列是指存在一个严格递增的下标序列 < i1, i2,…, ik>,使得 对于所有 j=1,2,…,k 有 Xij=Zj。例如,序列 Z=是序列 X=的子序列,相应的递 增下标序列为<2,3,5,7>。 给定两个序列 X 和 Y,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,称 Z 是序列 X 和 Y 的公共 子序列。 例如,若 X= < A, B, C, B, D, A, B>,Y= < B, D, C, A, B, A>,则序列是 X 和 Y 的一个公共子 序列,但它不是 X 和 Y 的一个最长公共子序列。序列也是 X 和 Y 的一个公共子序列,它的长 度为 4,而且它是 X 和 Y 的最长公共子序列,因为 X 和 Y 没有长度大于 4 的公共子序列。 给定两个序列 X= < x1, x2, …, xm>和 Y= < y1, y2, … , yn>,要求找出 X 和 Y 的最长公共子序列。 【输入文件】 输入文件共有两行,每行为一个由大写字母构成的长度不超过 200 的字符串,表示序列 X 和 Y。 【输出文件】 输出文件第一行为一个非负整数,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输 出文件仅有一行输出一个整数 0,否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字 母组成的字符串表示。 【输入样例】 ABCBDAB BDCBA 【输出样例】 4 BCBA 【提交链接】 http://poj.org/problem?id=1458 http://www.rqnoj.cn/Problem_164.html 【问题分析】 这个问题也是相当经典的。 这个题目的阶段很不明显,所以初看这个题目没什么头绪,不像前面讲的有很明显的上一步,上一层 之类的东西,只是两个字符串而且互相没什么关联。 但仔细分析发现还是有入手点的: 既然说是动态规划,那我们首先要考虑的就是怎么划分子问题,一般对于前面讲到的街道问题和数塔 问题涉及走向的,考虑子问题时当然是想上一步是什么?但这个问题没有涉及走向,也没有所谓的上一步, 该怎么办呢? 既然是求公共子序列,也就有第一个序列的第 i 个字符和第二个序列的第 j 个字符相等的情况。 那么我们枚举第一个序列(X)的字符,和第二个序列(Y)的字符。 显然如果 X[i]=Y[j]那么起点是 1(下面说的子序列都是起点为 1 的),长度为 i 的子序列和长度为 j 的 子序列的最长公共子序列就是长度为 i-1 和长度为 j-1 的子序列中最长的公共子序列加上 X[i]或 Y[j]。 那要是不相等呢? 如果不相等,也就是说第一个序列长度为 i 的子序列和第二个序列中长度为 j 的子序列的公共子序列 中 X[i]和 Y[j]不同时出现。也就是说第一个序列长度为 i 的子序列和第二个序列中长度为 j 的子序列的公共 子序列是第一个序列长度为 i 的子序列和第二个序列中长度为 j-1 的子序列或第一个序列长度为 i-1 的子序 列和第二个序列中长度为 j 的子序列的公共子序列中一个更长的。 设计一个状态 opt[i,j] 表示起点为 1,第一序列长度为 i,第二序列长度为 j 的子序列的最长公共子序 列。按照上面的分类就可以得到状态转移方程: opt[i-1,j-1]+x[i] (x[i]=y[j]) opt[i,j]= opt[i-1,j]+x[i] (length(opt[i-1,j])>=length(opt[i,j-1])) opt[i,j-1]+y[j] (length(opt[i-1,j])=length(opt[i,j- 1]) then opt[i,j]:=opt[i-1,j] else opt[i,j]:=opt[i,j-1]; end; procedure print; begin writeln(length(opt[L1,L2])); write(opt[L1,L2]); close(output); end; begin init; main; print; end. 例题 18 回文词 (palin.pas/c/cpp) 来源:IOI 2000 【问题描述】 回文词是一种对称的字符串——也就是说,一个回文词,从左到右读和从右到左读得到的结果是一样 的。任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。你的任务是写一个程序,求出将 给定字符串变成回文词所需插入的最少字符数。 比如字符串“Ab3bd”,在插入两个字符后可以变成一个回文词(“dAb3bAd”或“Adb3bdA”)。然而, 插入两个以下的字符无法使它变成一个回文词。 【输入文件】 第一行包含一个整数 N,表示给定字符串的长度,3<=N<=5000 第二行是一个长度为 N 的字符串,字符串由大小写字母和数字构成。 【输出文件】 一个整数,表示需要插入的最少字符数。 【输入样例】 5 Ab3bd 【输出样例】 2 【提交链接】 http://poj.org/problem?id=1159 【问题分析】 所谓回文词(正着读和反着读一样),其实就是从中间断开把后面翻转后与前面部分一样(注意奇数 和偶数有区别)。例: 回文词:AB3BA 断开:AB BA (奇数个时去掉中间字符) 翻转:AB AB 这个题目要求出最少填几个数可以使一个字符串变成回文词,也就是说从任意点截断,再翻转后面部 分后两个序列有相同的部分不用添字符,不一样的部分添上字符就可以了。例: 回文词:Ab3bd 截断:Ab bd 翻转:Ab db b 在两个序列里都有,在第二个里添 A 在第一个里添 d 就可以了: Adb Adb 这样添两个就可以了,显然从别的地方截断添的个数要比这样多。 这样就把原问题抽象成求最长公共子序列问题了。枚举截断点,把原串截断,翻转。求最长公共子序 列。答案就是 len-(ans*2) len 是翻转后两个序列的长度和。Ans 是最长公共子序列的长度。 其实这样求解很麻烦,做了好多重复的工作。仔细想想既然在最后求解 ans 还要乘 2 那么在先前计算 时直接把原串翻转作为第二个序列和第一个序列求最长公共子序列就可以了。这样最后求解就不用乘 2 了, 也不用枚举截断点了。例: 原串:Ab3bd 翻转:db3bA 最长公共子序列 b3b 添加 2 个字符 怎么理解这个优化呢? 其实翻转了序列后字符的先后顺序就变了,求解最长公共子序列中得到的解,是唯一的,也就是说这 个序列的顺序是唯一的,如果在翻转后的序列和原串能得到相同的序列,那么这个序列在两个串中字符间 的顺序是恒定的,这就满足了回文词的定义(正着读和反着读一样)。所以这个优化是正确的。 注意: 这个问题的数据规模很大,空间复杂度较高(O(N2))所以要用到滚动数组,如果不知道什么是滚动 数组就该往后翻页,因为我在后面的动态规划的优化里会说到。 【源代码 1】 program P1327; const maxn=5002; var a,b:ansistring; opt:array[0..1,0..maxn] of longint; n,ans:longint; function max(x,y:longint):longint; begin if x>y then exit(x); max:=y; end; procedure main; var i,x,j,k0,k1:longint; begin fillchar(opt,sizeof(opt),0); readln(n); readln(a); b:=''; for i:=n downto 1 do b:=b+a[i]; k0:=0; k1:=1; for i:=1 to n do begin fillchar(opt[k1],sizeof(opt[k1 ]),0); for j:=1 to n do begin opt[k1,j]:=max(opt[k0,j],opt[ k1,j-1]); if a[i]=b[j] then opt[k1,j]:=max(opt[k1,j],opt[ k0,j-1]+1); end; x:=k0; k0:=k1; k1:=x; end; writeln(n-opt[k0,n]); end; begin main; end. 用这个方法 AC 了就该很高兴了,但不要停止思考的步伐,还有别的方法么? 从原问题出发,找这个问题的子问题。和上面说的最长公共子序列问题一样,设计序列的问题我们一 般要考虑它的子序列,也就是更短的序列。 这样就回到了我第一节说的边界条件法了。 显然单独的字符就是边界了,而且单独的字符就是回文词,添加 0 个字符就可以了。 如果是两个字符组成的序列怎么办呢? 只要看他们是否相同就可以了,如果相同那就是回文词了,添加 0 个字符,如果不相同就在它的左边 或右边添一个字符,让另外一个当对称轴。 如果是 3 个字符呢? 我们用 S 存这个序列,如果 S[1]=S[3]那么它就是回文词了,如果 S[1]<>S[3],那么就在前面添 S[3] 或后面添 S[1],剩下的就要考虑 S[1]S[2]和 S[2]S[3]这两个序列了。 通过前面的分析我们很容易想到这样的算法: 对于一个序列 S 只要看它的左右端的字符是否相同,如果相同那么就看除掉两端字符的新串要添的字 符个数了;如果不同,就在它左面添上右端的字符,然后考虑去掉新序列两端的字符后的串要添的字符。 或者在右面添上左端的字符,再考虑去掉添了字符后新串左右两端字符得到的新串要添的字符。 设计一个二维状态 opt[L,i]表示长度是 L+1,起点是 i 的序列变成回文词要添的字符的个数。阶段就是 字符的长度,决策要分类,即 S[i] 和 S[i+L]是否相等。 状态转移方程: min(opt[L-1,i]+1, opt[L-1,i+1]+1) (s[i]<>s[i+L]) opt[L,i]= min(opt[L-1,i]+1, opt[L-1,i+1]+1,opt[L-2,i+1]) (s[i]=s[i+L]) 复杂度:空间复杂度=状态数 O(N2),时间复杂度=状态数 O(N2)* 转移代价 O(1)=O(N2)。由 于空间复杂度较高,仍然要用滚动数组。 【源代码 2】 program P1327; const maxn=5002; var a:array[0..maxn] of char; opt:array[0..2,0..maxn] of longint; n,ans:longint; function min(x,y:longint):longint; begin min:=y; if xa[j],1<=i0 说明花费 正好) 状态转移方程: opt[j,k]=max{opt[j-rmb[i],k-rp[i]]+1} (rmb[i]<=j<=m,rp[i]<=k<=r,00) ct[j,k]:=min{ct[j-rmb[i],k-rp[i]]}+time[i] (opt[j,k]=opt[j-rmb[i],k-rp[i]]+1) 时间复杂度:阶段数 O(N)*状态数 O(MR)*转移代价 O(1)= O(NMR)。 注:数据挺小的。 问题拓展: 如果要加入别的条件,比如泡 MM 还要一定的 SP 等,也就是说一个价值要不同的条件确定,那么这 个问题的状态就需要再加一维,多一个条件就多一维。 【源代码】 program gf; const fin='gf.in'; fout='gf.out'; maxn=110; var rmb,rp,time:array[0..maxn] of longint; opt,ct:array[0..maxn,0..maxn] of longint; n,m,r,ans,max:longint; procedure init; var i:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(n); for i:=1 to n do read(rmb[i],rp[i],time[i]); read(m,r); close(input); end; procedure main; var i,j,k:longint; begin fillchar(opt,sizeof(opt),0); fillchar(ct,sizeof(ct),0); opt[0,0]:=1; for i:=1 to n do for j:=m downto rmb[i] do for k:=r downto rp[i] do if opt[j-rmb[i],k-rp[i]]>0 then begin if opt[j-rmb[i],k-rp[i]]+1>opt[j,k] then begin opt[j,k]:=opt[j-rmb[i],k-rp[i]] +1; ct[j,k]:=ct[j-rmb[i],k-rp[i]]+ti me[i]; end else if (opt[j-rmb[i],k-rp[i]]+1=opt[j,k]) and (ct[j-rmb[i],k-rp[i]]+time[i]max then begin max:=opt[j,k]; ans:=ct[j,k]; end else if (opt[j,k]=max) and (ct[j,k]0),打分越高的碟说明多多越爱看。每 张碟有播放的时间 Ti。多多想在今晚爷爷规定的时间里看的碟总分最高。(必须把要看的碟看完,也就是 说一张碟不能只看一半)。显然叔叔在买碟时没必要把 N 张全买了,只要买要看的就 OK 了,这样节省资 金啊。而且多多让叔叔惯的特别任性,只要他看到有几张就一定会看完。 可是出现了一个奇怪的问题,买碟的地方只卖给顾客 M(My then max:=x; end; procedure main; var i,j,k:longint; begin fillchar(opt,sizeof(opt),0); for i:=1 to n do for j:=m downto 1 do if j<=i then for k:=v downto w[i] do if (opt[j-1,k-w[i]]>0) or ((j=1) and (k=w[i])) then opt[j,k]:=max(opt[j-1,k-w[i]] +val[i],opt[j,k]); ans:=-maxlongint; for i:=0 to v do if opt[m,i]>ans then ans:=opt[m,i]; end; procedure print; begin write(ans); close(output); end; begin init; main; print; end. 2.5 石子合并问题 也有人把这类问题叫做是区间上的动态规划。 例题 22 石子合并 (stone.pas/c/cpp) 来源:某年 NOI(去巴蜀交) 【问题描述】 在一个操场上摆放着一行共 n 堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆 合并成新的一堆,并将新的一堆石子数记为该次合并的得分。请编程计算出将 n 堆石子合并成一堆的最小 得分和将 n 堆石子合并成一堆的最大得分。 【输入文件】 输入第一行为 n(n<1000),表示有 n 堆石子,第二行为 n 个用空格隔开的整数,依次表示这 n 堆石子 的石子数量(<=1000) 【输出文件】 输出将 n 堆石子合并成一堆的最小得分和将 n 堆石子合并成一堆的最大得分。 【输入样例】 3 1 2 3 【输出样例】 9 11 【提交链接】 http://www.rqnoj.cn/Problem_490.html 【问题分析】 人们拿到这类题目的第一想法是贪心(找最大/最小的堆合并),但是很容易找到贪心的反例:(以求最 小为例) 贪心: 3 4 6 5 4 2 5 4 6 5 4 得分:5 9 6 5 4 得分:9 9 6 9 得分:9 15 9 得分:15 24 得分:24 总得分:62 合理方案 3 4 6 5 4 2 7 6 5 4 2 得分:7 7 6 5 6 得分:6 7 11 6 得分:11 13 11 得分:13 24 得分:24 总得分:61 也就是说第二个 4 和 2 合并要比和 5 合并好,但是由于一开始 2 被用了没办法它只好和 5 合并了…… 既然贪心不行,数据规模又很大,我们自然就想到用动态规划了。 *不过要知道某个状态下合并后得分最优就需要知道合并它的总得分,只有对子问题的总得分进行最 优的判断,设计的状态才有意义。 *但要是想知道总分,就要知道合并一次的得分,显然这个含义不能加到动态规划的状态中,因为一 般一个状态只代表一个含义(也就是说 OPT[i]的值只能量化一个问题)(上面带*号的两段比较抽象,不懂 可以不看。我只是为了标注自己的理解加的,不理解的也没必要理解。) 先要把题目中的环变成链,这样好分析问题。具体方法:把环截断,复制一份放到截断后形成的链的 后面形成一个长度是原来两倍的链(只有环中的元素在处理时不随着变化,就可以这样做。其实读入数据 已经帮你截断了); 例: 3 4 5 变成 3 4 5 3 4 5 对于这样一个链,我们设计一个状态 opt[i,j]表示起点为 i 终点为 j 的链合并成一堆所得到的最优得分。 要合并一个区间里的石子无论合并的顺序如何它的得分都是这个区间内的所有石子的和,所以可以用 一个数组 sum[i]存合并前 i 个石子的得分。 因为合并是连续的所以决策就是把某次合并看作是把某个链分成两半,合并只想把两半的好多堆分别 合并成一堆的总得分+最后合并这两半的得分。 状态转移方程: maxopt[i,j]=max{maxopt[i,k]+maxopt[k+1,j]}+sum[j]-sum[i-1] minopt[i,j]=min{minopt[i,k]+minopt[k+1,j]}+sum[j]-sum[i-1] 复杂度:状态数 O(N2)*决策数 O(N)=O(N3) 【源代码】 program stone; const maxn=1010; var a,sum:array[0..maxn] of longint; minopt,maxopt:array[0..max n*2,0..maxn*2] of longint; n:longint; minans,maxans:longint; procedure init; var i:longint; begin read(n); for i:=1 to n do begin read(a[i]); a[n+i]:=a[i]; end; for i:=1 to n*2 do sum[i]:=sum[i-1]+a[i]; end; function max(x,y:longint):longint; begin max:=y; if x>y then max:=x; end; function min(x,y:longint):longint; begin min:=y; if (x0) then min:=x; end; procedure main; var i,j,L,k:longint; begin fillchar(minopt,sizeof(minopt ),200); fillchar(maxopt,sizeof(maxop t),0); for i:=1 to 2*n do minopt[i,i]:=0; for L:=1 to n-1 do for i:=1 to 2*n-L do begin j:=i+L; for k:=i to j-1 do begin maxopt[i,j]:=max(maxopt[i,j] ,maxopt[i,k]+maxopt[k+1,j]); minopt[i,j]:=min(minopt[i,j], minopt[i,k]+minopt[k+1,j]); end; inc(maxopt[i,j],sum[j]-sum[i- 1]); inc(minopt[i,j],sum[j]-sum[i- 1]); end; maxans:=-maxlongint; minans:=maxlongint; for i:=1 to n do maxans:=max(maxans,maxo pt[i,i+n-1]); for i:=1 to n do minans:=min(minans,minopt[ i,i+n-1]); {for i:=1 to n*2 do begin for j:=1 to n*2 do write(maxopt[i,j],' '); writeln; end;} end; begin init; main; writeln(minans,' ',maxans); end. 例题 23 能量项链 (energy.pas/c/cpp) 来源 NOIP2006(提高组) 【问题描述】 在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有 头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记 一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是 Mars 人吸收能量的一种器官)的作用, 这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m, 尾标记为 r,后一颗能量珠的头标记为 r,尾标记为 n,则聚合后释放的能量为(Mars 单位),新产生的珠 子的头标记为 m,尾标记为 n。 需要时,Mars 人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。 显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。 例如:设 N=4,4 颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两 颗珠子的聚合操作,(j k)表示第 j,k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能 量为:(4 1)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为: ((4 1) 2) 3)=10*2*3+10*3*5+10*5*10=710。 【输入文件】 输入文件 energy.in 的第一行是一个正整数 N(4≤N≤100),表示项链上珠子的个数。第二行是 N 个 用空格隔开的正整数,所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记(1≤i≤N),当 i2 3 5 10 2 3 5 10 这样处理后其中任意长度为 N+1 的链就可代表一个环,那么问题就转化成合并任意长度为 N+1 的链 所能释放的总能量最大。 也就是说从任意一点(iy then exit(x); exit(y); end; procedure main; var i,j,k,L:longint; begin fillchar(opt,sizeof(opt),0); for L:=2 to n do for i:=1 to n*2-L+1 do begin j:=i+L; for k:=i+1 to j-1 do opt[i,j]:=max(opt[i,j],opt[i,k] +opt[k,j]+a[i]*a[j]*a[k]); end; for i:=1 to n do ans:=max(ans,opt[i,i+n]); end; procedure print; begin writeln(ans); close(output); end; begin init; main; print; end. 例题 24 统计单词个数 (.pas/c/cpp) 来源:NOIP2001(提高组) 【问题描述】 给出一个长度不超过 200 的由小写英文字母组成的字母串(约定:该字母串以每行 20 个字母的方式输 入,且保证每行一定为 20 个)。要求将此字母串分成 k 份(1y then max:=x; end; procedure main; var i,j,t:longint; begin L:=length(s); for i:=L downto 1 do for j:=i to L do if find(i,j) then sum[i,j]:=sum[i+1,j]+1 else sum[i,j]:=sum[i+1,j]; fillchar(opt,sizeof(opt),0); opt[1]:=sum[1]; for i:=2 to k do for j:=i+1 to L do for t:=i+1 to j-1 do opt[i,j]:=max(opt[i,j],opt[i-1,t ]+sum[t+1,j]); writeln(opt[k,L]); end; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); init; main; close(input); close(output); end. 2.6 其他问题 还有一些题目虽和一写基本模型相似但又有区别,我也就不总结共性了,列出它们,看看他们的状态 又是怎么设计的: 例题 25 花店橱窗设计 (flower.pas/c/cpp) 来源:IOI 或巴蜀评测系统 【问题描述】假设以最美观的方式布置花店的橱窗,有 F 束花,每束花的品种都不一样,同时,至少 有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,并从左到右,从 1 到 V 顺序编号,V 是 花瓶的数目,编号为 1 的花瓶在最左边,编号为 V 的花瓶在最右边,花束可以移动,并且每束花用 1 到 F 的整数惟一标识,标识花束的整数决定了花束在花瓶中列的顺序即如果 I < J,则花束 I 必须放在花束 J 左 边的花瓶中。 例如,假设杜鹃花的标识数为 1,秋海棠的标识数为 2,康乃馨的标识数为 3,所有的花束在放人花瓶 时必须保持其标识数的顺序,即:杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花 瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空,即每个花瓶中只能放一束花。 每一个花瓶的形状和颜色也不相同,因此,当各个花瓶中放人不同的花束时会产生不同的美学效果,并以 美学值(一个整数)来表示,空置花瓶的美学值为 0。在上述例子中,花瓶与花束的不同搭配所具有的美学 值,可以用如下表格表示。 根据表格,杜鹃花放在花瓶 2 中,会显得非常好看,但若放在花瓶 4 中则显得很难看。 为取得最佳美学效果,必须在保持花束顺序的前提下,使花的摆放取得最大的美学值,如果具有最大美 学值的摆放方式不止一种,则输出任何一种方案即可。题中数据满足下面条件:1≤F≤100,F≤V≤100, -50≤AIJ≤50,其中 AII 是花束 I 摆放在花瓶 J 中的美学值。输入整数 F,V 和矩阵(AIJ),输出最大美学 值和每束花摆放在各个花瓶中的花瓶编号。 花瓶 1 花瓶 2 花瓶 3 花瓶 4 花瓶 5 杜鹃花 7 23 -5 -24 16 秋海棠 5 21 -4 10 23 康乃馨 -21 5 -4 -20 20 【输入文件】 第一行包含两个数:F,V。 随后的 F 行中,每行包含 V 个整数,Aij 即为输入文件中第(i+1 )行 中的第 j 个数 【输出文件】 包含两行:第一行是程序所产生摆放方式的美学值。第二行必须用 F 个数表示摆放方式,即该行的第 K 个数表示花束 K 所在的花瓶的编号。 【输入样例】 3 5 7 23 –5 –24 16 5 21 -4 10 23 -21 5 -4 -20 20 【输出样例】 53 2 4 5 【题目链接】 http://poj.org/problem?id=1157 http://www.rqnoj.cn/Problem_496.html 【问题分析】 这个问题很奇怪题目中给定的条件是花瓶和花束,似乎是两个没有关联的事物啊,但着两个看似没关 联的东西,却有一点联系:不同的花放在不同的花瓶中产生不同的美学价值。 一般人的思维都是拿来花一个一个的放,假设要放第 i 束花时,把它放到哪里好呢? 很容易想到一个贪心的策略:找到一个符合条件(第 i 束花要放在前 i-1 束花的后面)下的它放如后能 产生最大的美学价值的花瓶放。但和容易举出反例: 花瓶 1 花瓶 2 花瓶 3 杜鹃花 1 2 -5 秋海棠 5 10 1 按照贪心策略是:杜鹃花放在 2 号瓶里,秋海棠放在 3 号瓶里,美学值:3 答案是:杜鹃花放在 1 号瓶里,秋海棠放在 2 号瓶里,美学值:11 数据量很大搜索显然不行。 那要是动态规划,阶段,状态,决策有是什么呢? 既然要拿来花束一个一个的放,我们就以花束划分阶段。设计一个状态 opt[i,j]表示将第 i 束花放在第 j 个花瓶中可使前 i 束花或得的最大美学价值,那么决策就很容易想到了:将第 i 束花放在第 j 个瓶中,那 么第 i-1 束花只能放在前 j-1 个瓶里,显然我们要找到一个放在前 j-1 个瓶中的一个最大的美学价值在加上 当前第 i 束放在第 j 个瓶中的美学价值就是 OPT[I,J]的值。 显然符合最优化原理和无后效性。 状态转移方程: opt[i,j]=max{opt[i-1,k]}+a[i,j] (i<=k<=j-1) 为什么是 i<=呢? 复杂度:状态数 O(FV)*转移代价 O(V)=O(FV2) 数据范围很小,可以在瞬间出解。 回顾刚才的解题过程,贪心和动态规划都是找前一阶段的最大值,为什么贪心是错的,而动态规划是 对的呢? 着就要读者自己反思,总结了。 【源代码】 const maxn=110; var a,opt,path:array[0..maxn,0..m axn] of longint; n,m,ans:longint; procedure init; var i,j:longint; begin read(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); end; procedure main; var i,j,k:longint; begin for i:=1 to n do for j:=1 to m do opt[i,j]:=-maxlongint; for i:=1 to n do for j:=i to m-n+i do begin for k:=i-1 to j-1 do if opt[i-1,k]>opt[i,j] then begin opt[i,j]:=opt[i-1,k]; path[i,j]:=k; end; inc(opt[i,j],a[i,j]); end; ans:=n; for i:=n+1 to m do if opt[n,i]>opt[n,ans]then ans:=i; end; procedure outputway(i,j:longint); begin if i>0 then begin outputway(i-1,path[i,j]); write(j,' '); end; end; procedure print; var i:longint; begin writeln(opt[n,ans]); outputway(n,ans); writeln; end; begin init; main; print; end. 例题 26 Divisibility 来源:ZJU2042 【问题描述】 Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 16 17 + 5 + -21 - 15 = -14 17 + 5 - -21 + 15 = 58 17 + 5 - -21 - 15 = 28 17 - 5 + -21 + 15 = 6 17 - 5 + -21 - 15 = -24 17 - 5 - -21 + 15 = 48 17 - 5 - -21 - 15 = 18 We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5. You are to write a program that will determine divisibility of sequence of integers. 译题: 给出 N 个数,你可以在这 N 个数中任意地添加+号或-号,求解能不能使算出的结果被 K 整除。可以 则打印“Divisible”,否则打印“Not divisible”。(1 <= N <= 10000, 2 <= K <= 100) 下面是一个例子:有 4 个数,分别是 17 5 -21 15,有 8 种添法,其中第二种求出的-14 能被 7 整除。 17 + 5 + -21 + 15 = 16 17 + 5 + -21 - 15 = -14 17 + 5 - -21 + 15 = 58 17 + 5 - -21 - 15 = 28 17 - 5 + -21 + 15 = 6 17 - 5 + -21 - 15 = -24 17 - 5 - -21 + 15 = 48 17 - 5 - -21 - 15 = 18 【输入文件】 The first line of the input contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space. The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value. 注意第一个数是测试数据的组数,多组测试数据一起测。 【输出文件】 Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not. The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks. The output format consists of N output blocks. There is a blank line between output blocks. 注意:输出每组结果之间有空格,最后一行无空格,格式不对不能 AC,我就是因为格式不对调了一 上午… 【输入样例】 2 4 7 17 5 -21 15 4 5 17 5 -21 15 【输出样例】 Divisible Not divisible 【提交链接】 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2042 http://poj.org/problem?id=1745 【问题分析】 看到题目第一个反映就是枚举中间添的运算符,算出值在 MOD K 如果有一个值 MOD K=0 则输出 “Divisible”。 时间复杂度是 O(2N-1)。 但是题目给出的数据量很大,这样做效率太低了。因为题目涉及 MOD 运算,要想简化问题就需要知 道一些基本的 MOD 运算性质: A*B mod C=(A mod C*B mod C) mod C (A+B) mod C=(A mod C+B mod C) mod C 有了这个性质,我们就可以把累加后求余转化成求余后累加(我们把减法看作加负数以后分析只说加 法)再求余。这样我们的读入数据就控制在了 1-K 到 K-1 的范围内了。 我们要判断的就是:所有结果的累加和 MOD K 是否为 0。简记为: (A+B)mod K=0 or (A+B) mod K<>0 如果我们按数的个数划分阶段,前 N-1 个数的运算结果 MOD K 看做 A,第 N 个数看作 B 就 OK 了。 于是我们想到了这样的状态:opt[i,j]表示前 i 个数是否可以得到余数为 J 的结果。 那么状态转移方程就是: opt[i,(j-a[i] mod k )mod k]=opt[i-1,j] (opt[i-1,j]=true); opt[i,(j+a[i] mod k) mod k]=opt[i-1,j] (opt[i-1,j]=true); 如果 opt[n,0]=true 就输出‘Divisible’。 【源代码】 program P2042; const maxk=110; maxn=10010; var a:array[0..maxn] of longint; opt:array[1..2,-maxk..maxk] of boolean; n,k,tim,ii:longint; vis:array[0..maxn] of boolean; procedure init; var i:longint; begin read(n,k); for i:=1 to n do read(a[i]); end; procedure main; var i,j,p1,p2,p3:longint; begin fillchar(opt,sizeof(opt),false); fillchar(vis,sizeof(vis),false); for i:=1 to n do if a[i] mod k=0 then vis[i]:=true; for i:=1 to n do a[i]:=a[i] mod k; opt[1,a[1]]:=true; p1:=1; p2:=2; for i:=2 to n do if not vis[i] then begin fillchar(opt[p2],sizeof(opt[p2 ]),false); for j:=1-k to k-1 do if opt[p1,j] then begin opt[p2,(j-a[i]) mod k]:=true; opt[p2,(j+a[i]) mod k]:=true; end; p3:=p1; p1:=p2; p2:=p3; end; if opt[p1,0] then writeln('Divisible') else writeln('Not divisible'); end; begin read(tim); for ii:=1 to tim do begin if ii>1 then writeln; init; main; end; end. 3.多维状态和动态规划的优化 一般多维动态规划的时,空间复杂度较高,所以我们要想办法将其优化,我就把多维动态规划和动态 规划的优化放到一起了…… 多维动态规划以三,四维最为常见,在多的也没有太大的研究价值,其实多维动态规划大多也就是上 面的一维,和二维的加一些条件,或是在多进程动态规划中要用到。当然除了这些特点外,状态的表示也 有一些共性。 三维:状态 opt[i,j,k]一般可表示下面的含义: (1)二维状态的基础上加了某个条件,或其中一维变成两个。 比如 opt[L,i]表示起点为 I,长度为 L 的序列的最优值。opt[L,i,j]就可表示起点是 i 和起点是 j,长度是 L 的两个序列的最优值。 (2)I,J,K 组合表示一个正方形((i,j)点为一角,边长为 K)。 (3)I,J,K 组合表示一个等边三角形((i,j)点为一角,边长为 K)。 四维:除了二维和三维加条件外,还可以用 i,j,k,t 组合来描述一个矩形, (i,j)点和(k,t)点是两个对顶点。 四维以上的一般都是前几维加了条件了,这里就不多说了。 动态规划的优化: 动态规划的优化往往需要较强的数学功底。 常见空间优化: 滚动数组,滚动数组在前面也提到过,其实很简单,如果一个状态的决策的步长为 N 就只保留以求出 的最后 N(一般 N=1)个阶段的状态,因为当前状态只和后 N 个阶段中的状态有关,再以前的已经利用过 了,没用了就可以替换掉了。具体实现是最好只让下标滚动(这样更省时间)。 X:=K1,K1:=K2,K2;=K3,K3:=X 这样就实现了一个 N=3 的下标的滚动,在滚动完如果状态 是涉及累加,累乘类的操作要注意将当前要求的状态初始化。 常见时间优化:利用一些数据结构(堆,并查集,HASH)降低查找复杂度。 时间空间双重优化:改变状态的表示法,降低状态维数。 具体的多维动态规划和动态规划的优化,我们从题目里体会吧! 3.1 矩阵问题 先看一道题 例题 27 盖房子 来源:VIJOS P1057 【问题描述】 永恒の灵魂最近得到了面积为 n*m 的一大块土地(高兴 ING^_^),他想在这块土地上建造一所房子, 这个房子必须是正方形的。但是,这块土地并非十全十美,上面有很多不平坦的地方(也可以叫瑕疵)。 这些瑕疵十分恶心,以至于根本不能在上面盖一砖一瓦。他希望找到一块最大的正方形无瑕疵土地来盖房 子。不过,这并不是什么难题,永恒の灵魂在 10 分钟内就轻松解决了这个问题。现在,您也来试试吧。 【输入文件】 输入文件第一行为两个整数 n,m(1<=n,m<=1000),接下来 n 行,每行 m 个数字,用空格隔开。0 表 示该块土地有瑕疵,1 表示该块土地完好。 【输出文件】 一个整数,最大正方形的边长。 【输入样例】 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 【输出样例】 2 【提交链接】 http://www.vijos.cn/Problem_Show.asp?id=1057 【问题分析】 题目中说要求一个最大的符合条件的正方形,所以就想到判断所有的正方形是否合法。 这个题目直观的状态表示法是 opt[i,j,k]基类型是 boolean,判断以(i,j)点为左上角(其实任意一个角 都可以,依据个人习惯),长度为 K 的正方形是否合理,再找到一个 K 值最大的合法状态就可以了(用 true 表示合理,false 表示不合理)。其实这就是递推,(决策唯一)。 递推式: opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1) 时间复杂度: 状态数 O(N3)*转移代价 O(1)=总复杂度 O(N3) 空间复杂度: O(N3) 由于空间复杂度和时间复杂度都太高,不能 AC,我们就的再想想怎么优化? 显然何以用滚动数组优化空间,但是时间复杂度仍然是 O(N3)。这就需要我们找另外一种简单的状 态表示法来解了。 仔细分析这个题目,其实我们没必要知道正方形的所有长度,只要知道以一个点为左上角的正方形的 最大合理长度就可以了。 如果这个左上角是 0 那么它的最大合理长度自然就是 0(不可能合理)。 如果这个左上角是 1 呢? 回顾上面的递推式,我们考虑的是以它的右面,下面,右下这个三个方向的正方形是否合理,所以我 们还是要考虑这三个方向。具体怎么考虑呢? 如果这三个方向合理的最大边长中一个最小的是 X,那么它的最大合理边长就是 X+1。为什么呢? 看个例子: 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 上例中红色的正方形,以(1,3)点为左上角,以(1,4),(2,3),(2,4)这三个点的最大合理边长 分别是 2,1,2。其中最小的是以(2,3)为左上角的正方形,最大合理边长是 1。因为三个方向的最大 合理边长大于等于 1,所以三个方向上边长为 1 的正方形是合理的,即上面低推式中: opt[1,3,2]=opt[1,4,1] and opt[2,3,1] and opt[2,4,1] and (a[1,3]=1) = true 成立 这样就把一个低推判定性问题转化成最优化问题从而节省空间和时间。 具体实现: 设计一个状态 opt[i,j]表示以(i,j)为左上角的正方形的最大合理边长。 状态转移方程: min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1 (a[i,j]=1) opt[i,j]=0 (a[i,j]=0) 时间复杂度:状态数 O(N2)*转移代价 O(1)=总代价 O(N2) 空间复杂度:O(N2) 【源代码】 program P1057; const maxn=1010; var opt,a:array[0..maxn,0..maxn] of longint; n,m,ans:longint; procedure init; var i,j:longint; begin read(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); for i:=n downto 1 do for j:=m downto 1 do if a[i,j]<>0 then begin opt[i,j]:=opt[i+1,j]; if opt[i,j+1]ans then ans:=opt[i,j]; writeln(ans); end; begin init; main; end. 3.2 多进程动态规划 从字面上就可以看出,所谓多进程就是在原文题的基础上要求将这个问题重复多次的总和最大。 具体怎么做看个例题吧。 例题 28 方格取数 (fgqs.pas/c/cpp) 来源:NOIP2000(提高组) 【问题描述】 设有 N*N 的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 0。如下 图所示(见样例): 某人从图的左上角的 A 点出发,可以向下行走,也可以向右走,直到到达右下角的 B 点。在走过的 路上,他可以取走方格中的数(取走后的方格中将变为数字 0)。 此人从 A 点到 B 点共走两次,试找出 2 条这样的路径,使得取得的数之和为最大。 【输入文件】 输入的第一行为一个整数 N(表示 N*N 的方格图),接下来的每行有三个整数,前两个表示位置,第 三个数为该位置上所放的数。一行单独的 0 表示输入结束。 【输出文件】 只需输出一个整数,表示 2 条路径上取得的最大的和。 【输入样例】 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 【输出样例】 67 【提交链接】 http://www.rqnoj.cn/Problem_314.html 【问题分析】 这是一道很经典的多进程动态规划题,如果只取一次,它的模型就是我们前面讲的街道问题了,很简 单就可以实现。现在要求取两次,怎么办呢? 一个自然的想法是:将前面的取过的数全赋成 0,然后在取一次,感觉挺对的,样例也过了。 但这样做是错的,第一次取的显然是最大值,但第二次取的未必次大,所以也许两条非最大的路,也 许比一条最大一条小一点的路更优。 看个例子: 0 0 2 0 3 0 0 0 2 0 3 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 2 0 2 0 0 0 2 0 2 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 2 0 2 0 0 0 2 0 2 0 图 1 图 2 如上图,图 1 是按找上诉思路求得的解。图中红色路线是第一求得的最大值,显然图 1 红色和紫色两 条路径不如图 2 蓝色和绿色两条路径大。 既然这样做不行,我们还得回到动态规划的本质来看代问题,我们在想想这个问题的状态,对于走一 次,走到矩阵的任意一个位置就是一个状态,而要是走两次,显然走到矩阵的某个位置只是一个状态的一 部分,不能完整的描述整个状态。那另一部分显然就是第二次走到的位置了。如果我们把这两部分合起来 就是一个完整的状态了。 于是,设计一个状态 opt[i1,j1,i2,j2]表示两条路分别走到(i1,j1)点和(i2,j2)点时取到的最大值。显 然决策有 4 中(乘法原理一个点两种*另一个点的两中) 即(上,上)(上,左)(左,上)(左,左)上和左表示从哪个方向走到该点,当然要注意走到同行, 同列,同点时的情况(因为要求路径不重复)。 状态转移方程: max(opt[i1-1,j1,i2-1,j2],opt[i1,j1-1,i2-1,j2])+a[i1,j1]+a[i2,j2] (1<=i1=i2<=n,1<=j1<=j2<=n) max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1]) (1<=j1=j2<=n,1<=i1<=i2<=n) opt[i,j]= max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2], opt[i1,j1-1,i2,j2-2])+a[i1,j1]+a[i2,j2] (1<=i1,j1<=i2,j2<=n) max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2], opt[i1,j1-1,i2,j2-2])+a[i1,j1] (1<=i1=i2<=n,1<=j1=j2<=n) 时间复杂度:状态数 O(N4)*转移代价 O(1)=总复杂度 O(N4) 空间复杂度:O(N4) 由于数据很小所以这样做虽然时间和空间复杂度都很高但还是可以 AC 的。 【源代码 1】 program fgqs; const fin='fgqs.in'; fout='fgqs.out'; maxn=11; var a:array[0..maxn,0..maxn] of longint; opt:array[0..maxn,0..maxn,0.. maxn,0..maxn] of longint; n:longint; procedure init; var i,j,w:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(n); repeat readln(i,j,w); a[i,j]:=w; until i=0; close(input); end; function max(x,y:longint):longint; begin max:=y; if x>y then max:=x; end; procedure main; var i1,i2,j1,j2:longint; begin for i1:=1 to n do for j1:=1 to n do for i2:=i1 to n do for j2:=1 to j1 do if (i1=i2) and (j1=j2) then opt[i1,j1,i2,j2]:=opt[i1-1,j1,i2 ,j2-1]+a[i1,j1] else if (i1=i2-1) and (j1=j2) then opt[i1,j1,i2,j2]:=max(opt[i1-1 ,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1]) +a[i1,j1]+a[i2,j2] else if (i1=i2) and (j1=j2+1) then opt[i1,j1,i2,j2]:=max(opt[i1-1 ,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2]) +a[i1,j1]+a[i2,j2] else begin opt[i1,j1,i2,j2]:=max(opt[i1-1 ,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2]); opt[i1,j1,i2,j2]:=max(opt[i1,j 1,i2,j2],opt[i1,j1-1,i2,j2-1]); opt[i1,j1,i2,j2]:=max(opt[i1,j 1,i2,j2],opt[i1,j1-1,i2-1,j2]); inc(opt[i1,j1,i2,j2],a[i1,j1]+a[ i2,j2]); end; end; procedure print; begin writeln(opt[n,n,n,n]); close(output); end; begin init; main; print; end. 如果这个题的数据范围在大点就得优化了,怎么优化这个程序呢? 上面说过对于时间空间都大的时候,首先想到的就是寻找特点,改变状态的表示法,减少状态的维数。 仔细分析我们发现,处于同行,同列的状态,等价于另外一个点在对角线上的状态。而这条对角线正 是此题的阶段。因为在状态转移的时候后面的哪个点总是从固定的一个方向转移来的。也就是说我们只要 对角先上的状态就可以省掉那些同行同列的状态了。 做过 N 皇的同学一定知道怎么表示右上到左下的这几条对角线,不知道的同学也没关系,对于一个点 (i,j)他对角右上角的点就是(i-1,j+1)所以可以看出这些点的和是定值,且值从 2 到 N*2。 这样用三个变量就可以表示这两个点了,于是设计状态 opt[k,i1,i2]表示处于阶段 K 时走到 i1,i2 的两条 路径所取得的数的最大和。 用上面的思维不难想出动态转移方程: max(opt[k-1,i1-1,i2-1],opt[k-1,i1-1,i2],opt[k-1,i1,i2-1],opt[k-1,i1,i2])+a[i1,k-i1]+a[i2,k-i2](1<=i1,i2<=n,2<= k<=n*2,i1<>i2) otp[k,i1,i2]=opt[k-1,i1-1,i2]+a[i1,k-i1](1<=i1,i2<=n,2<=k<=n*2,i1=i2) 【源代码 2】 program fgqs; const fin='fgqs.in'; fout='fgqs.out'; maxn=11; var a:array[0..maxn,0..maxn] of longint; opt:array[0..maxn*2,0..maxn, 0..maxn] of longint; n:longint; procedure init; var i,j,w:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(n); repeat readln(i,j,w); a[i,j]:=w; until i=0; close(input); end; function max(x,y:longint):longint; begin max:=y; if x>y then max:=x; end; procedure main; var k,i1,i2,j1,j2,mid:longint; begin for k:=2 to n*2 do begin for i1:=1 to n do if (k-i1>0) and (k-i1<=n) then for i2:=1 to n do if (k-i2>0) and (k-i2<=n) then begin if i1=i2 then opt[k,i1,i2]:=opt[k-1,i1-1,i2] +a[i1,k-i1] else begin opt[k,i1,i2]:=max(opt[k-1,i1,i 2],opt[k-1,i1,i2-1]); opt[k,i1,i2]:=max(opt[k,i1,i2] ,opt[k-1,i1-1,i2]); opt[k,i1,i2]:=max(opt[k,i1,i2] ,opt[k-1,i1-1,i2-1]); inc(opt[k,i1,i2],a[i1,k-i1]+a[i 2,k-i2]); end; end; end; end; procedure print; begin writeln(opt[n*2,n,n]); close(output); end; begin init; main; print; end. 注:如果取多次,和取两次道理一样,只不过有多一次,状态就多加一维,如果数据范围很大,时间 空间复杂度太高时可以用网络流解这个问题,只是本人才疏学浅不能和大家分享了。 4.树型动态规划 由于树型动态规划比较特殊,要借助树这种数据结构,所以很多地方都把它独立看做一类,我也不例 外。 一般树型动态规划都是建立在二叉树上的,对于普通的树和森林要把它们转化成二叉树,以前认为数 据结构中将的转化没什么用处,现在终于用到了。 树型动态规划是动态规划类中最好分析的,因为树本来就是一个低归的结构,阶段,状态,决策都很 明显,子问题就是子树的最优值,也很明显。 较其他类型的动态规划不同的是,求解树型动态规划的第一步一般要先建立数据结构,考虑问题的数 据结构是二叉树呢?还是多叉树,还是森林…… 其他类型的动态规划一般都是用逆向递推实现,而树型动态规划一般要正向求解,为了保证时间效率 要加记忆化(即长说的记忆化搜索)。 树型动态规划的三要素: 阶段:树的层数 状态:树中的结点 决策:某个子数的最优,或所有子树的最优和,或某几个子树的最优 通过上面的决策,发现如果是一棵多叉树,针对求某几个(>=1)子树的最优解,决策会很多。以至 于我们没发写出准确的状态转移方程。这就是我们为什么要把多叉数转化成二叉数的原因。(当然,如果 问题是求所有子树的和,就没必要转化了,如 URAL P1039 没有上司的舞会)。 如果把多叉树或森林转化成二叉树要注意,左儿子和根结点是父子关系,而右儿子在原问题中和跟结 点是兄弟关系。(这个数据结构掌握扎实的应该能明白,不理解的就去看数据结构方面的知识)。 用邻接矩阵存多叉树,转化成二叉树的部分代码(可能有语法错误) G: 存图,F[i] 表示第 i 个结点的儿子应该插入的位置 W:结点的值 BT:二叉树 Procedure creat_tree(T:tree); Var i:longint; Begin for i:=1 to n do Begin for j:=1 to n do If g[i,j] then Begin If F[i]=0 then BT[i].L:=j Else BT[F[i]].r:=j; F[i]:=j; End; End; End; 下面同过例题看一下树型动态规划的具体实现: 例题 29 加分二叉树 (binary.pas/c/cpp) 来源:NOIP2003(提高组) 【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为(l,2,3,…,n),其中数字 1,2,3,…,n 为节点编号。每个节点 都有一个分数(均为正整数),记第 i 个节点的分数为 di,tree 及它的每个子树都有一个加分,任一棵子树 subtree(也包含 tree 本身)的加分计算方法如下: subtree 的左子树的加分× subtree 的右子树的加分+subtree 的根的分数 若某个子树为空,规定其加分为 1,叶子的加分就是叶节点本身的分数。不考虑它的空 子树。 试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树 tree。要求输出; (1)tree 的最高加分 (2)tree 的前序遍历 【输入格式】 第 1 行:一个整数 n(n<30),为节点个数。 第 2 行:n 个用空格隔开的整数,为每个节点的分数(分数<100)。 【输出格式】 第 1 行:一个整数,为最高加分(结果不会超过 4,000,000,000)。 第 2 行:n 个用空格隔开的整数,为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 3 1 2 4 5 【提交链接】 http://www.rqnoj.cn/Problem_49.html 【问题分析】 根据题目描述就可以看出是典型的树型动态规划,而且题目中已经给出了加分的求法: subtree 的左子树的加分× subtree 的右子树的加分+subtree 的根的分数 这估计是最简单的题目了。 但是有一点需要注意:我们应该怎么建树? 其实这个题不用建树,这就需要我们对数据结构掌握的很扎实。 题目中说这个树的中序遍历是 1,2,3……N,我们要求的是树的先序,这样马上就想到怎样用中序 和先序确定一棵树。 枚举树根 i 那么 1,2……i-1 就是它的左子树中的结点,i+1……N 就是它右子树中的结点。这样一颗 树按这样的低归定义就构造出来了,(当然我们只要这个过程并不需要存储这棵树)。在构造过程中顺便求 出加分来,在一个序列里不同的元素做根显然加分不同,我们只要记录一个最大的就可以了。 具体实现方法: 设计状态 opt[L,r]表示以 L 为起点,以 r 为终点的结点所组成的树的最高加分,阶段就是树的层数。决 策就是在这些结点中找一个结点做根使树的加分最大,状态转移方程: 1 (L>r) opt[L,r] = a[L] (L=r) max{opt[L,i-1]*opt[i+1,r]+a[i]} (Lr then begin opt[L,r]:=1; path[L,r]:=0; end else if L=r then begin opt[L,r]:=a[L]; path[L,r]:=L; end else begin for i:=L to r do begin x:=TreeDp(L,i-1)*TreeDp(i+ 1,r)+a[i]; if x>opt[L,r] then begin opt[L,r]:=x; path[L,r]:=i; end; end; end; end; TreeDp:=opt[L,r]; end; procedure print(L,r:longint); begin if path[L,r]>0 then begin write(path[L,r],' '); print(L,path[L,r]-1); print(path[L,r]+1,r); end; end; begin init; writeln(TreeDp(1,n)); print(1,n); close(output); end. 例题 30 A Binary Apple Tree 苹果二叉树 来源:URAL P1018 【问题描述】 设想苹果树很象二叉树,每一枝都是生出两个分支。我们用自然数来数这些枝和根那么必须区分不 同的枝(结点),假定树根编号都是定为 1,并且所用的自然数为 1 到 N。N 为所有根和枝的总数。例如下 图的 N 为 5,它是有 4 条枝的树。 2 5 \ / 3 4 \ / 1 当一棵树太多枝条时,采摘苹果是不方便的,这就是为什么有些枝要剪掉的原因。现在我们关心的是, 剪枝时,如何令到损失的苹果最少。给定苹果树上每条枝的苹果数目,及必须保留的树枝的数目。你的任 务是计算剪枝后,能保留多少苹果。 【输入文件】 首行为 N,Q (1 <= Q <= N, 1 < N <= 100), N 为一棵树上的根和枝的编号总数,Q 为要保留的树枝 的数目。以下 N-1 行为每条树枝的描述,用 3 个空格隔开的整数表示,前 2 个数为树枝两端的编号,第三个 数为该枝上的苹果数。假设每条枝上的苹果数不超过 3000 个。 【输出文件】 输出能保留的苹果数。(剪枝时,千万不要连根拔起哦) 【输入样例】 5 2 1 3 1 1 4 10 2 3 20 3 5 20 【输出样例】 21 【问题分析】 和上一道题一样,题目描述就很明确的说是关于树的题目,在加上是求最优值,和上一道题不同的是, 这个题目边有值,并非点有值,还有一个不同点就是这个题需要建树。 建树是要注意,给每个结点增加一个域:SUM 用来存以它为根的树中的边的数目。 其实树型动态规划是最好分析的,因为树这种数据结构本来就符合递归定义,这样的话子问题很好找, 显然这个问题的子问题就是一棵树要保留 M 个枝分三种情况: 剪掉左子树:让右子树保留 M-1 个枝可保留最多的苹果数+连接右子树的枝上的苹果数 剪掉右子树:让左子树保留 M-1 个枝可保留最多的苹果数+连接左子树的枝上的苹果数 都不剪掉: 让左子树保留 i 个枝,让右子树保留 M-2-i 个枝可保留最多的苹果数+连接右子树的枝上 的苹果数+连接左子树的枝上的苹果数 显然边界条件就是如果要保留的枝子数比当前的子树的枝多,或着一个树要保留 0 个枝子,则结果就 是 0。 应为一颗树中根接点是对子树的完美总结,所以满足最优化原理。 没次求解只和子树有关所以也满足无后效性,可见用动态规划做是正确的。 设计一个状态 opt[num,i]表示要让结点编号为 i 的树保留 num 个枝可得到的最优解。 状态转移方程: opt[num,i]=max{opt[num-1,BT[i].L]+T[i,BT[i].L],opt[num-1,BT[i].r]+T[i,BT[i].r],opt[k,BT[i].L]+opt[num- 2-k,BT[i].r]+T[i,BT[i].L]+T[i,BT[i].r]} (0<=k<=n-2,BT:树,T:读入时记录的枝上的苹果数); 时间复杂度:状态数 O(NM)*转移代价 O(M)=O(NM2) 【源代码】 program P1018; const fin='P1018.in'; fout='P1018.out'; maxn=110; type treetype=record l,r,sum:longint; end; var T,opt:array[0..maxn,0..maxn] of longint; BT:array[0..maxn] of treetype; vis:array[0..maxn] of boolean; n,m,p:longint; procedure init; var i,j,k,w:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); fillchar(T,sizeof(T),0); read(n,m); for k:=1 to n-1 do begin read(i,j,w); T[i,j]:=w; T[j,i]:=w; end; close(input); fillchar(vis,sizeof(vis),false); end; Procedure creat_tree(i:longint); var j:longint; begin vis[i]:=true; for j:=1 to n do if (T[i,j]>0) and (not vis[j]) then begin creat_tree(j); BT[i].L:=Bt[i].r; Bt[i].r:=j; inc(Bt[i].sum,BT[j].sum+1); end; end; Function max(x,y:longint):longint; begin max:=y; if x>y then max:=x; end; Function F(num,i:longint):longint; var k:longint; begin if opt[num,i]<0 then begin if (num>BT[i].sum) or (num=0) then opt[num,i]:=0 else begin opt[num,i]:=F(num-1,BT[i].L )+T[i,BT[i].L]; opt[num,i]:=max(opt[num,i], F(num-1,BT[i].r)+T[i,BT[i].r]); for k:=0 to num-2 do opt[num,i]:=max(opt[num,i], F(k,BT[i].L)+F(num-2-k,BT[i].r) +T[i,BT[i].L]+T[i,BT[i].r]); end; end; F:=opt[num,i]; end; begin init; creat_tree(1); fillchar(opt,sizeof(opt),200); writeln(F(m,1)); close(output); end. 动态规划经典问题 刘汝佳 目录 一、最长公共子序列O(mn) 二、最优排序二叉树O(n3) 三、最长上升子序列O(nlogn) 四、最优三角剖分O(n3) 五、最大m子段和O(mn) 六、0-1背包问题O(min{nc, 2n, n1.44n}) 七、最优排序二叉树O(n2) 八、最优合并问题O(nlogn) 一、最长公共子序列 • Longest Common Subsequence(LCS) 分析 • 考虑前缀x[1..i]和y[1..j], 定义 c[i,j] = |LCS(x[1..i], y[1..j])| • 则c[m,n] = |LCS(x, y)|. 递推公式为 • 很直观. 考虑x[i]=y[j]的情形: 关键点一: 最优子结构 • 为了使用动态规划, 问题需具备最优子结构 (Optimal Substructure) 直接书写的程序 递归树分析 关键点二: 重叠子问题 • 为了让动态规划确实发挥功效, 问题应该包含尽 量多的重叠子问题(overlapping subproblems) 解决方法: 记忆化 • 注意memoization不是memorization 自底向上递推 空间优化 • 如果只需要最优值, 可以用滚动数组实现 • 按照i递增的顺序计算, d[i,j]只和d[i-1,j]和 d[i,j-1]以及d[i-1,j-1]有关系,因此只需要保 留相邻两行, 空间复杂度为O(min{m,n}) • 更进一步的, 可以只保留一行, 每次用单独 的变量x保留d[i-1,j], 则递推方程为 If(i==j) d[j]=x; else { x = d[j]; d[j]=max{d[j-1], d[j]} }; 变形. 回文词 • 给一个字符串a, 保持原字符的顺序不变, 至 少要加几个字符才能变成回文词? • 例: abfcbfa Î afbcfcbfa 分析 • 红、绿色表示原字符, 白色为新增字符 • 显然, s和s’在任何一个位置不可能都是白色(不 需要加那个字符!) • 应该让红色字符尽量多! 相当于求s和逆序串s’ 的LCS, 让LCS中的对应字符(红色)对齐, 中间的 每个绿色字符都增加一个字符和它相等 二、最优排序二叉树 • 给n个关键码和它们的频率,构造让期望比 较次数最小的排序二叉树 分析 • 定理:最优排序二叉树的子树也是最优排 序二叉树 • 给出关键码-频率对照表(升序排列) • 问题:把哪个关键码做为根?则左右子树 可以递归往下做 ABCDE 23 10 8 12 30 FGHIJKLMNOP.. 5 14 18 20 2 4 11 7 22 22 10 .. 分析 • 用递归来思考,但用递推来做 • 先考虑两个结点的情形 分析 • 可以用矩阵来保存结果 • C[j,k]表示从j到k的关键码组成的最优排序二叉树 • Root[j,k]记录这棵排序二叉树的根 分析 • 考虑三个结点的情形 • 最优值放在C[B,D]中,根放在root[B,D]中 分析 • 类似地,更新所有C[j-2,j]和root[j-2,j] 分析 • 四个结点的情形(如A-D) 分析 • 最终计算结果为 分析 • 可以利用root矩阵递归地构造出最优树 分析 • 时间复杂度:计算每个C[i,j]和root[i,j]需要 枚举根结点,故为O(n3) • 空间复杂度:需要两个n*n矩阵,O(n2) 三、最长上升子序列 • 最长上升子序列问题(LIS)给一个序列, 求它的一个递增子序列,使它的元素个数 尽量多。例如序列1,6,2,5,4,7的最长上升子 序列是1,2,5,7(还有其他的,这里略去) 分析 • 定义d[i]是从第1个元素到第i个元素为止的最长子 序列长度, 则状态转移方程为 • 直接使用这个方程得到的是O(n2)算法 • 下面把它优化到O(nlogn) 状态的组织 •d值相同的a值只需要保留最小的, 因此用数 组g[i]表示d值为i的数的a最小值, 显然 g[1]<=g[2]<=…<=g[k] • 计算d[i]: 需要在g中找到大于等于a[i]的第 一个数j, 则d[i]=j • 更新g: 由于g[j]>a[i], 需要更新g[j]=a[i] 代码 • 使用STL的lower_bound可以直接求出比a[i] 大的第一个数, 用二分查找实现, 每次转移 时间O(logn), 总时间O(nlogn) fill(g, g + n, infinity); for(inti=0;ivj, 则j 是不需要保存的, 因此按重量排序好以后也是按价 值排序的 • 考虑后一半元素时, 每得到一个重量w, 用二分查 找得到重量不超过c-w的最大元素, 则它的价值也 最大. • 预处理时间复杂度2n/2log2n/2, 每个重量w二分查找 时间为log2n/2, 因此总2n/2log2n/2=O(n1.44n) 七、再谈最优排序二叉树 • 给n个关键码和它们的频率,构造让期望比 较次数最小的排序二叉树 基本分析 • 设结点i..j的最优代价为d[i,j], 则 • 其中w[i,j]=fi+fi+1+…+fj,(如果认为根结点的代价为0, 则w[i,j]要减去fk). 直接计算是O(n3)的 • 设d[i,j]的最优决策为K[i,j], 下面证明 K[i,j-1]<=K[i,j]<=K[i+1,j] • 从而把时间复杂度降到O(n2) 四边形不等式 • 凸性(Monge condition/quadrangle inequality) w[i,j]+w[i’j’]<=w[i’,j]+w[i,j’], i<=i’j时类似 情形2. 非退化的情形 • i’y两种情况(对称). 下面只考虑z<=y时 •y和z是合法决策,因此y<=j, z>i, 且 d[i,j]<=w[i,j]+d[i,z-1]+d[z,j] d[i’,j’]<=w[i’,j’]+d[i’,y-1]+d[y,j’] • 两式相加并整理, 对应项写在一起, 得 情形2. 非退化的情形 • 两式相加并整理, 对应项写在一起, 右边<= w[i,j]+w[i’,j’]+d[i,z-1]+d[i’,y-1]+d[z,j]+d[y,j’] • 因z<=y, 红蓝色分别用四边形不等式, 右边<= w[i,j’]+w[i’,j]+d[i,z-1]+d[i’,y-1]+d[z,j’]+d[y,j] • 按红蓝色分别组合, 得 d[i,j]+d[i’,j’]<=d[i,j’]+d[i’,j] •z<=y时命题得证. z>y时类似 决策单调性 • 进一步地, d的凸性可以推出决策的单调性 • 设k[i,j]为让d[i,j]取最小值的决策, 下面证明 k[i,j]<=k[i,j+1]<=k[i+1,j+1], i<=j • 即: k在同行同列上都是递增的 • 证明: i=j时显然成立. 由对称性, 只需证明 k[i,j]<=k[i,j+1]. 记dk[i,j]=d[i,k-1]+d[k,j]+w[i,j], 则只需要证明对于所有的i=0)Îk’在[i,j+1]上也更优(右>=0) • 设k’是[i,j]的最优值,则对于它左边的任意k, k’在 [i,j]更优可推出k’在[i,j+1]上也更优, 因此在区间 [I,j+1]上, k’左边的值都比它大, 如下图 决策单调性 • 欲证dk[i,j]-dk’[i,j]<=dk[i,j+1]-dk’[i,j+1], 移项得 dk[i,j]+dk’[i,j+1]<=dk[i,j+1]+dk’[i,j] • 按定义展开, 两边消去w[i,j]+w[i,j+1], 得 d[i,k-1]+d[k,j]+d[i,k’-1]+d[k’,j+1]<= d[i,k-1]+d[k,j+1]+d[i,k’-1]+d[k’,j] • 同时消去红色部分,得 d[k,j]+d[k’,j+1]<=d[k,j+1]+d[k’,j] • 这就是k<=k’<=j
还剩113页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 5 人已下载

下载pdf

pdf贡献者

cgs6654820

贡献于2017-06-06

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!