nbhkdz.com冰点文库

高中计算机竞赛 编程 动态规划解析辅导


第二节

动态规划

动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不 象前面所述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方 法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解 的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不

存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学习时,除了要对基 本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创 造性的技巧去求解。 我们也可以通过对若干有代表性的问题的动态规划算法进行分析、 讨论, 逐渐学会并掌握这一设计方法。

一、 动态规划的基本模型 (一)多阶段决策过程的最优化问题
在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的 阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当然,各个 阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶 段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线,如下图所 示:

这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过 程,这种问题就称为多阶段决策问题。 例 3-2-1 :最短路径问题。下图给出了一个地图,地图中的每个顶点代表一个城市, 两个城市间的一条连线代表道路, 连线上的数值代表道路的长度。 现在想从城市 A 到达城市 E,怎样走路程最短?最短路程的长度是多少?

分析:把 A 到 E 的全过程分成四个阶段,用 K 表示阶段变量,第 1 阶段有一个初始状态 A,有两条可供选择的支路 A-B1、A-B2;第 2 阶段有两个初始状态 B1、B2,B1 有三条可供 选择的支路,B2 有两条可供选择的支路??。用 DK(XI,X+1J)表示在第 K 阶段由初始状态

XI 到下阶段的初始状态 X+1J 的路径距离, FK (XI) 表示从第 K 阶段的 XI 到终点 E 的最短距离, 利用倒推的方法,求解 A 到 E 的最短距离。具体计算过程如下: S1 : K = 4 有 F4(D1)= 3, F4(D2)= 4, F4(D3)= 3; S2 : K = 3 有 F3(C1)= MIN{ D3(C1,D1)+ F4(D1) ,D3(C1,D2)+ F4(D2)} = MIN{ 5+3,6+4 } = 8, F3(C2)= D3(C2,D1)+ F4(D1)= 5+3 = 8; F3(C3)= D3(C3,D3)+ F4(D3)= 8+3 = 11; F3(C4)= D3(C4,D3)+ F4(D3)= 3+3 = 6; S3 : K = 2 有 F2(B1)= MIN{ D2(B1,C1)+ F3(C1) ,D2(B1,C2)+ F3(C2) , D2(B1,C3)+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9, F2(B2)= MIN{ D2(B2,C2)+ F3(C2) ,D2(B2,C4)+ F3(C4)} = MIN{ 8+8,4+6 } = 10; S4 : K = 1 有 F1(A)= MIN{ D1(A,B1)+ F2(B1) ,D1(A,B2)+ F2(B2)} = MIN{ 5+9,3+10} = 13。 因此由 A 点到 E 点的全过程最短路径为 A→B2→C4→D3→E;最短路程长度为 13。 从以上过程可以看出, 每个阶段中, 都求出本阶段的各个初始状态到终点 E 的最短距离, 当逆序倒推到过程起点 A 时,便得到了全过程的最短路径和最短距离。 在上例的多阶段决策问题中,各个阶段采取的决策,一般来说是与阶段有关的,决策依 赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故 有“动态”的含义,我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。

(二)动态规划的基本概念和基本模型构成
现在我们来介绍动态规划的基本概念。 1. 阶段和阶段变量: 用动态规划求解一个问题时,需要将问题的全过程恰当地分成若干个相互联系的阶 段,以便按一定的次序去求解。描述阶段的变量称为阶段变量,通常用 K 表示,阶段的 划分一般是根据时间和空间的自然特征来划分,同时阶段的划分要便于把问题转化成多 阶段决策过程,如例题 3-1-1 中,可将其划分成 4 个阶段,即 K = 1,2,3,4。 2. 状态和状态变量: 某一阶段的出发位置称为状态,通常一个阶段包含若干状态。一般地,状态可由变 量来描述,用来描述状态的变量称为状态变量。如例题 3-1-1 中,C3 是一个状态变量。 3. 决策、决策变量和决策允许集合: 在对问题的处理中作出的每种选择性的行动就是决策。即从该阶段的每一个状态出 发,通过一次选择性的行动转移至下一阶段的相应状态。一个实际问题可能要有多次决 策和多个决策点,在每一个阶段的每一个状态中都需要有一次决策,决策也可以用变量 来描述,称这种变量为决策变量。在实际问题中,决策变量的取值往往限制在某一个范 围之内,此范围称为允许决策集合。如例题 3-1-1 中,F3(C3)就是一个决策变量。

4.策略和最优策略: 所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体 称为策略。在实际问题中,从决策允许集合中找出最优效果的策略成为最优策略。 5. 状态转移方程 前一阶段的终点就是后一阶段的起点,对前一阶段的状态作出某种决策,产生后一 阶段的状态, 这种关系描述了由 k 阶段到 k+1 阶段状态的演变规律, 称为状态转移方程。 在上面介绍的动态规划基本概念的基础上,可以得到动态规划的基本模型构成如下: 确定问题的决策对象。 对决策过程划分阶段。 对各阶段确定状态变量。 根据状态变量确定费用函数和目标函数。 建立各阶段状态变量的转移过程,确定状态转移方程。

1. 2. 3. 4. 5.

(三)最优化原理与无后效性
上面已经介绍了动态规划模型的基本组成,现在需要解决的问题是:什么样的“多阶段 决策问题”才可以采用动态规划的方法求解。 一般来说,能够采用动态规划方法求解的问题,必须满足最优化原理和无后效性原则: 1. 动态规划的最优化原理。作为整个过程的最优策略具有:无论过去的状态和决策如何, 对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略的性质。也可以通俗 地理解为子问题的局部最优将导致整个问题的全局最优,即问题具有最优子结构的性 质,也就是说一个问题的最优解只取决于其子问题的最优解,而非最优解对问题的求解 没有影响。在例题 3-1-1 最短路径问题中,A 到 E 的最优路径上的任一点到终点 E 的路 径,也必然是该点到终点 E 的一条最优路径,即整体优化可以分解为若干个局部优化。 2. 动态规划的无后效性原则。所谓无后效性原则,指的是这样一种性质:某阶段的状态一 旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说,“未来与过去 无关” ,当前的状态是此前历史的一个完整的总结,此前的历史只能通过当前的状态去 影响过程未来的演变。在例题 3-1-1 最短路径问题中,问题被划分成各个阶段之后,阶 段 K 中的状态只能由阶段 K+1 中的状态通过状态转移方程得来,与其它状态没有关系, 特别与未发生的状态没有关系,例如从 Ci 到 E 的最短路径,只与 Ci 的位置有关,它是 由 Di 中的状态通过状态转移方程得来,与 E 状态,特别是 A 到 Ci 的路径选择无关,这 就是无后效性。 由此可见,对于不能划分阶段的问题,不能运用动态规划来解;对于能划分阶段,但不 符合最优化原理的,也不能用动态规划来解;既能划分阶段,又符合最优化原理的,但不具 备无后效性原则, 还是不能用动态规划来解; 误用动态规划程序设计方法求解会导致错误的 结果。

二、

动态规划的设计与实现

(一)动态规划设计方法的一般模式
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段 决策的选择,达到结束状态;或倒过来,从结束状态开始,通过对中间阶段决策的选择,达 到初始状态。这些决策形成一个决策序列,同时确定了完成整个过程的一条活动路线,通常

是求最优活动路线。 动态规划的设计都有着一定的模式,一般要经历以下几个步骤: 1. 划分阶段:按照问题的时间或空间特征,把问题划分为若干个阶段。在划分阶段时,注 意划分后的阶段一定是有序的或者是可排序的,否则问题就无法求解。 2. 确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表 示出来。当然,状态的选择要满足无后效性。 3. 确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根 据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也 就可以写出。但事实上常常是反过来做,根据相邻两段的各个状态之间的关系来确定决 策。 4. 寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条 件。 5. 程序的设计实现:一旦设计完成,实现就会非常简单。下面我们给出从初始状态开始, 通过对中间阶段决策的选择,达到结束状态,按照阶段、状态和决策的层次关系,写出 的程序流程的一般形式: 所有状态费用的初始化; for i := 阶段最大值-1 downto 1 do {倒推每一个阶段} for j := 状态最小值 to 状态最大值 do {枚举阶段 i 的每一个状态} for k := 决策最小值 to 决策最大值 do {枚举阶段 i 中状态 j 可选择的每一种决策} begin f[i,j] ← min{d[i,j,k] + f[i+1,k]} end; 输出 f[1,1]; 例 3-2-1 对应的 Pascal 程序如下: var d : array[1..4,1..4,1..4] of byte; f : array[1..5,1..4] of byte; i,j,k,min : byte; begin fillchar(d,sizeof(d),0); d[1,1,1] := 5; d[1,1,2] := 3; d[2,1,1] := 1; d[2,1,2] := 6; d[2,1,3] := 3; d[2,2,2] := 8; d[2,2,4] := 4; d[3,1,1] := 5; d[3,1,2] := 6; d[3,2,1] := 5; d[3,3,3] := 8; d[3,4,3] := 3; d[4,1,1] := 3; d[4,2,1] := 4; d[4,3,1] := 3; fillchar(f,sizeof(f),255); f[5,1] := 0;

for i := 4 downto for j := 1 to 4 for k := 1 to if d[i,j,k] if f[i,j] writeln(f[1,1]); readln; end.

1 do do 4 do <> 0 then > d[i,j,k]+f[i+1,k] then f[i,j] := d[i,j,k]+f[i+1,k];

(二)动态规划方法实现的灵活性与技巧性
这里需要说明的是,上述程序流程仅是提供了解题的一种思路或方法,并不是说所有解 题的程序流程都应如此。例如: ● 若每一个阶段仅一个出发位置,则可通过一重循环枚举各个阶段的状态; ● 若状态非一个整数值所能描述(例如代表平面或空间上的一个坐标),则枚举状态的第 二重循环可由相应的多重循环替代; ● 如果可供选择的决策较少或者较难定义决策序号,则取消枚举决策的第三重循环,将 决策过程直接放入状态转移方程或者在循环体内编写决策选择程序; 我们必须从问题本身和解题需求出发,具体问题具体分析,制定行之有效的策略。特别 是作为信息学竞赛中的动态规划问题,考察的知识面是多方面的,应用的技巧也是多变的。 例 3-2-2 :拦截导弹。某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但 是这种拦截系统有一个缺陷: 虽然它的第一发炮弹能够到达任意的高度, 但是以后每一发炮 弹都不能高于前一发的高度。 某天, 雷达捕捉到敌国的导弹来袭, 由于该系统还在试用阶段。 所以只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度不大于 30000 的正整数)。计算这套系统最多 能拦截多少导弹。 输入:依次飞来的导弹高度(1≤N≤1000)。 输出:一套系统最多拦截的导弹数,并依次打印输出被拦截导弹的高度。 在本题中不仅要求输出最优解,而且还要求输出最优解的形成过程。为此,我们设置了 一张记忆表 C[i],在按从后往前方式求解的过程中,将每一个子问题的最佳决策保存起来, 避免在输出方案时重复计算。 阶段 i:由右而左计算导弹 n‥导弹 1 中可拦截的最多导弹数(1≤i≤n) ; 状态 B[i]:由于每个阶段中仅一个状态,因此可通过一重循环 for i := n-1 downto 1 do 枚举每个阶段的状态 B[i]; 决策 k:在拦截导弹 i 之后应拦截哪一枚导弹可使得 B[i]最大(i+1≤k≤n) , var a,b,c : array[1..1000] of word; n,i,j,k,max : word; begin writeln('INPUT : '); {初始化,读入数据} n := 0; while not eoln do begin

inc(n); read(a[n]); b[n] := 1; c[n] := 0; end; readln; for i := n-1 downto 1 do begin {枚举每一个阶段的状态,设导弹 i 被拦截} max := 0; j := 0; for k := i+1 to n do {枚举决策,计算最佳方案中拦截的下一枚导弹} if (a[k] <= a[i]) and (b[k] > max) then begin max := b[k]; j := k; end; b[i] := max+1; c[i] := j; {若导弹 i 之后拦截导弹 j 为最佳方案,则记下} end; max := 0; for i := 1 to n do {枚举求出一套系统能拦截的最多导数} if b[i] > max then begin max := b[i]; j := i; end; writeln('OUTPUT'); {打印输出结果} writeln('Max = ',b[j]); while j > 0 do begin write(a[j]:5); j := c[j]; end; readln; end. 上面的两道例题都是倒推的,决策的选择也较多。下面我们来讲一题是正推的,而且决 策的选择较少。 例 3-2-3 :数塔问题。设有一个三角形的数塔,如下图所示。顶点结点称为根结点, 每个结点有一个整数数值,其值不超过 100。从顶点出发,可以向左走,也可以向右走。

从根 13 出发,向左走到达 11,再向右走到达 7,再向左走到达 14,再向左到达 7。由 于 7 是最底层, 无路可走。 此时, 我们找到一条从根结点开始到达底层的路径: 13-11-7-14-7。 路径上结点中数字的和,称为路径的值,如上面路径的值为 13+11+7+14+7 = 52。 当三角形数塔给出之后, 找出一条路径, 使路径上的值为最大, 打印输出最大路径的值。 数塔的层数 N 最多可为 100。 算法分析: 此题贪心法往往得不到最优解,例如 13-11-12-14-13 其路径的值为 63,但这不是最优

解。 穷举搜索往往是不可能的,当层数 N = 100 时,路径条数 P = 2 这是一个非常大的数, 即使用世界上最快的电子计算机,也不能在短时间内计算出来。 对这道题唯一正确的方法是动态规划。如果得到一条由顶到底的某处的一条最佳路径, 那么对于该路径上的每一个中间点来说,由顶至该中间点的路径所经过的数字和也为最大。 因此本题是一个典型的多阶段决策最优化问题。在本题中仅要求输出最优解,为此我们设置 了数组 A[i,j]保存三角形数塔,B[i,j]保存状态值,按从上往下方式进行求解。 阶段 i:以层数来划分阶段,由从上往下方式计算层数 1‥层数 N(1≤i≤n) ;因此可 通过第一重循环 for i := 1 to n do begin 枚举每一阶段; 状态 B[i,j]:由于每个阶段中有多个状态,因此可通过第二重循环 for j := 1 to i do begin 求出每个阶段的每个状态的最优解 B[i,j]; 决策:每个状态最多由上一层的两个结点连接过来,因此不需要做循环。 var a,b : array[1..100,0..100] of word; i,j,n : byte; max : word; begin repeat write('N = '); readln(n); until n in [1..100]; fillchar(a,sizeof(a),0); b := a; for i := 1 to n do begin for j := 1 to i do read(a[i,j]); readln; end; b[1,1] := a[1,1]; for i := 2 to n do for j := 1 to i do if b[i-1,j-1] > b[i-1,j] then b[i,j] := b[i-1,j-1]+a[i,j] else b[i,j] := b[i-1,j]+a[i,j]; max := 0; for i := 1 to n do if b[n,i] > max then max := b[n,i]; writeln('Max = ',max); readln; end.
99

三、多姿多彩的动态规划
动态规划是一种重要的程序设计思想, 具有广泛的应用价值, 在信息学竞赛中经常出现。

使用动态规划思想来设计程序, 对于不少问题的解决往往具有高时效。 动态规划之所以具有 高时效,是因为它在将问题规模不断减小的同时,有效地把一系列的局部最优解记录下来, 从而避免了反复解同一个子问题的现象。 因而对于能够使用动态规划思想来解决的问题, 使 用动态规划是比较明智的选择。 动态规划是一种很灵活的解题方法,对不同的问题,有各具特色的解题方法,而不存在 一种不变的动态规划算法,因此动态规划是多姿多彩的。在动态规划思想的程序设计中,要 深刻理解动态规划的本质,同时要多实践,不但要多解题,还要学会从解题中探寻规律,总 结技巧。 动态规划是用空间换时间的一种方法的抽象。 其关键是发现子问题和记录其结果。 然后 利用这些结果减轻运算量。 比如 01 背包问题: /* 一个旅行者有一个最多能用 M 公斤的背包,现在有 N 件物品, 它们的重量分别是 W1,W2,...,Wn, 它们的价值分别为 P1,P2,...,Pn. 若每种物品只有一件求旅行者能获得最大总价值。 输入格式: M,N W1,P1 W2,P2 ...... 输出格式: X */ 因为背包最大容量 M 未知。所以,我们的程序要从 1 到 M 一个一个的试。比如,开始任选 N 件物品的一个。看对应 M 的背包,能不能放进去,如果能放进去,并且还有多的空间,则, 多出来的空间里能放 N-1 物品中的最大价值。怎么能保证总选择是最大价值呢?看下表。 测试数据: 10,3

3,4 4,5 5,6

c[i][j]数组保存了 1,2,3 号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为 0 开始,1 号物品先试,0,1,2,的容量都不能放. 所以置 0,背包容量为 3 则里面放 4.这样,这一排背包容量为 4,5,6,....10 的时候,最佳方 案都是放 4.假如 1 号物品放入背包.则再看 2 号物品.当背包容量为 3 的时候,最佳方案还 是上一排的最价方案 c 为 4.而背包容量为 5 的时候,则最佳方案为自己的重量 5.背包容量 为 7 的时候,很显然是 5 加上一个值了。加谁??很显然是 7-4=3 的时候.上一排 c3 的最佳 方案是 4.所以。 总的最佳方案是 5+4 为 9.这样.一排一排推下去。 最右下放的数据就是最大 的价值了。(注意第 3 排的背包容量为 7 的时候,最佳方案不是本身的 6.而是上一排的 9.说 明这时候 3 号物品没有被选.选的是 1,2 号物品.所以得 9.) 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚 了吗? 下面是实际程序: #include<stdio.h> int c[10][100];/*对应每种情况的最大价值*/ int knapsack(int m,int n) { int i,j,w[10],p[10]; for(i=1;i<n+1;i++) scanf("\n%d,%d",&w[i],&p[i]); for(i=0;i<10;i++)

for(j=0;j<100;j++) c[i][j]=0;/*初始化数组*/ for(i=1;i<n+1;i++) for(j=1;j<m+1;j++) { if(w[i]<=j) /*如果当前物品的容量小于背包容量*/ { if(p[i]+c[i-1][j-w[i]]>c[i-1][j]) /*如果本物品的价值加上背包剩下 的空间能放的物品的价值*/ /*大于上一次选择的最佳方案则更 新 c[i][j]*/ c[i][j]=p[i]+c[i-1][j-w[ i]]; else c[i][j]=c[i-1][j]; } else c[i][j]=c[i-1][j]; } return(c[n][m]);

} int main() { int m,n;int i,j;

scanf("%d,%d",&m,&n); printf("Input each one:\n"); printf("%d",knapsack(m,n)); printf("\n");/*下面是测试这个数组,可删除*/ for(i=0;i<10;i++) for(j=0;j<15;j++) { printf("%d ",c[i][j]); if(j==14)printf("\n"); } system("pause"); }

例 3-2-4 演讲大厅安排: 有一个演讲大厅需要我们管理,演讲者们事先定好了需要演讲的起始时间和中止时间。 我们想让演讲大厅得到最大可能的使用。 我们要接受一些预定而拒绝其他的预定, 目标是使 演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束,另一个演讲就可以立即开始。 问题求解: 1、 从文本文件 HALL.IN 中读入演讲者的申请。 2、 计算演讲大厅最大可能的使用时间。 3、 将结果写入文件 HALL.OUT。 输入文件(HALL.IN) : 输入文件 HALL.IN 第一行为一个整数 N,N≤5000,表示申请的数目。 以下 n 行每行包含两个整数 p,k,1 ≤ p < k ≤ 10000,表示这个申请的起始时间和 中止时间。 输出文件(HALL.OUT) : 输出文件 HALL.OUT 包含一个整数,表示大厅最大可能的使用时间。 输入输出示例: HALL.IN 12 1 2 3 5 0 4

6 8 7 13 4 6 9 10 9 12 11 14 15 19 14 16 18 20 HALL.OUT 16 var a : array[1..5000] of integer; t : array[0..5000,1..2] of integer; n,i,j,max : integer; begin assign(input,'hall.in'); reset(input); assign(output,'hall.out'); rewrite(output); readln(n); for i := 1 to n do readln(t[i,1],t[i,2]); for i := 1 to n-1 do for j := i+1 to n do if t[i,2] > t[j,2] then begin t[0] := t[i]; t[i] := t[j]; t[j] := t[0]; end; for i := 1 to n do begin max := 0; for j := 1 to i-1 do if (a[j] > max) and (t[i,1] >= t[j,2]) then max := a[j]; a[i] := max+t[i,2]-t[i,1]; end; max := 0; for i := 1 to n do if a[i] > max then max := a[i]; writeln(max); close(input); close(output); end. 例 3-2-5 方格取数: 设有 N×N 的方格图,我们将其中的某些方格中填入正整数,而其它的方格中则放入数 字 0。如下图所示:

A 0 0 0 0 0 0 0 0 0 0 0 0 21 0 14 0 0 13 0 0 0 15 0 0 0 0 0 14 0 0 0 0 0 0 7 0 0 0 0 0 0 6 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

B 某人从图中的左上角的 A 出发,可以向下行走,也可以向右行走,直到达右下角的 B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 0) 。 问题求解: 此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。 输入文件(TAKE.IN) : 输入文件 TAKE.IN 第一行为一个整数 N(N≤10) ,表示 N×N 的方格图。 接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该 列上所放的数。一行 0 0 0 表示结束。 输出文件(TAKE.OUT) : 输出文件 TAKE.OUT 包含一个整数,表示两条路径上取得的最大的和。 输入输出示例: TAKE.IN 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 TAKE.OUT 67 const dx : array[1..2] of integer = (0,1); dy : array[1..2] of integer = (1,0); var m,g : array[1..10,1..10] of integer; n,i,j,k : integer; max,tt : longint; function doing : longint;

var i,j : integer; begin for i := 2 to n do begin g[1,i] := g[1,i]+g[1,i-1]; g[i,1] := g[i,1]+g[i-1,1]; end; for i := 2 to n do for j := 2 to n do if g[i,j-1] > g[i-1,j] then g[i,j] := g[i,j]+g[i,j-1] else g[i,j] := g[i,j]+g[i-1,j]; doing := g[n,n] end; procedure sub(x,y : integer; t : longint); var u : byte; v : integer; begin if (x = n) and (y = n) then begin g := m; tt := doing; if t+tt > max then max := t+tt; end else for u := 1 to 2 do if (x+dx[u] <= n) and (y+dy[u] <= n) then begin v := m[x+dx[u],y+dy[u]]; m[x+dx[u],y+dy[u]] := 0; sub(x+dx[u],y+dy[u],t+v); m[x+dx[u],y+dy[u]] := v; end; end; begin assign(input,'take.in'); reset(input); assign(output,'take.out'); rewrite(output); ReadLn(n); fillchar(m,sizeof(m),0); repeat readln(i,j,k); if (i = 0) and (j = 0) and (k = 0) then break; m[i,j] := k; until false; max := 0; sub(1,1,m[1,1]);

writeln(max); close(input); close(output); end. 例 3-2-6 蛙人: 一个蛙人现在拥有一些潜水用的特殊器材。 这些器材均为一些圆筒, 每一个圆筒中都包 含两个部分, 一部分装氧气, 另一部分装氮气。 现在我们给出每个圆筒的氮气和氧气的含量, 还有它们的重量,试根据蛙人所需的两种气体的数量计算出蛙人所需携带的最少的重量。 示例:假设这个蛙人拥有如下 5 个圆筒,每一个圆筒中氧气、氮气的含量(升)和它的 重量都用一行三个整数来表示如下:
3 36 120 10 25 129 5 50 250 1 45 130 4 20 119

如果该蛙人需要 5 升的氧气和 60 升的氮气, 那么它至少需要带 2 个总重 249 的圆筒 (例 如它取第一个和第二个圆筒或第四个和第五个圆筒) 。 问题求解: ? 从文本文件 PLE.IN 中读入圆筒的数目和每个圆筒中氧气、氮气的含量及它的重量; ? 计算为了满足蛙人的需要他所需携带的最少重量; ? 把结果输出到文本文件 PLE.OUT 中。 注释:我们给出的数据总是保证可以满足蛙人的需要的。 输入文件(PLE.IN) : 文本文件 PLE.IN 的第一行包括用空格分开的两个整数 t 和 a,1≤t≤21 且 1≤a≤79, 表示蛙人所需的氧气和氮气的体积。第二行包括一个整数 n,1≤n≤1000,为不同圆筒的数 目。以下的 n 行每行包括一个对圆筒的描述,第 i+2 行包括三个用空格分开的整数 ti、ai、 wi,分别表示第 i 个圆筒中氧气、氮气的含量和该圆筒的重量。 输出文件(PLE.OUT) : 你的程序应该在文本文件 PLE.OUT 中输出唯一的一个整数, 表示为了满足蛙人的要求, 它所需携带的最少重量。 输入输出样例: PLE.IN
5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119

PLE.OUT
249

var

t,a,n,tt,aa,ww,i,j,k,ni,nj : integer; w : array [0..21,0..79] of longint; begin assign(input,'ple.in'); reset(input); assign(output,'ple.out'); rewrite(output); read(t,a,n); fillchar(w,sizeof(w),$FF); w[0,0] := 0; for k := 1 to n do begin read(tt,aa,ww); for i := t downto 0 do for j := a downto 0 do if w[i,j] >= 0 then begin if i+tt > t then ni := t else ni := i+tt; if j+aa > a then nj := a else nj := j+aa; if (w[ni,nj] < 0) or (w[i,j]+ww < w[ni,nj]) then w[ni,nj] := w[i,j]+ww; end; end; writeln(w[t,a]); close(input); close(output); end. ----------------------------------------------蛙人程序二:

f[i,j,k]=min{f[i,j,k-1],f[i-x[k],j-y[k],k-1]}(两个数必须存在)
var a:array[0..21,0..79]of longint; b:array[1..1000,1..3]of longint; x,y,n,i,j,k:longint; begin assign(input,'ple.in');reset(input); assign(output,'ple.out');rewrite(output); readln(x,y,n); for i:=0 to 21 do for j:=0 to 79 do a[i,j]:=10000000; a[0,0]:=0; for i:=1 to n do begin readln(b[i,1],b[i,2],b[i,3]); for j:=21-b[i,1] downto 0 do for k:=79-b[i,2] downto 0 do

begin if a[j,k]>a[j,k+1] then a[j,k]:=a[j,k+1]; if a[j,k]>a[j+1,k] then a[j,k]:=a[j+1,k]; if a[j+b[i,1],k+b[i,2]]>a[j,k]+b[i,3] then a[j+b[i,1],k+b[i,2]]:=a[j,k]+b[i,3]; end; end; writeln(a[x,y]); close(input);close(output); end.

------------------------------------蛙人程序三:

做法: 01 背包 f[i,j]表示带 i 升氧气与 k 升氮气所需最少重量,很易得出 f[i,j]=min(f[i-a,j-b]+c) 代码: var n,m,k,y,d,a,b,c,i,min:longint; f:array[0..81,0..81] of longint; begin readln(n,m); readln(k); fillchar(f,sizeof(f),125); min:=maxlongint; f[0,0]:=0; for i:=1 to k do begin readln(a,b,c); for y:=80 downto a do for d:=80 downto b do begin if f[y,d]>f[y-a,d-b]+c then f[y,d]:=f[y-a,d-b]+c; if (y>=n) and (d>=m) then if f[y,d]<min then min:=f[y,d]; end; end; writeln(min); end.

例 3-2-7 乘积最大: 设有一个长度为 N 的数字串(N ≤ 50) ,我们要求使用 K 个乘号,将其分成 K+1 份。 问题求解:

找出一种分法,使得这 K+1 部分的乘积为最大。 例如:K = 1,数字串为 312 时会有以下两种分法: 1) 3*12 = 36 2) 31*2 = 62 这时,符合题目要求的结果是:62 输入文件(PRODUCT.IN) : 输入文件的第一行为一个整数 K(K ≤ 10) 。第二行为数字串。 输出文件(PRODUCT.OUT) : 输出文件包含一个整数,表示求得的最大乘积。 输入输出示例: PRODUCT.IN 3 310143 PRODUCT.OUT 3720 var p : array[0..10,1..50] of string[50]; i,j,k,n,t : integer; s,s1,max : string; function pd(a,b : string) : boolean; begin if length(a) > length(b) then pd := true else if length(a) < length(b) then pd := false else if a > b then pd := true else pd := false; end; function cf(a,b : string) : string; var c,d,e : array[1..52] of byte; i,j,la,lb : integer; g,h : string[50]; begin fillchar(c,sizeof(c),0); d := c; e := c; la := length(a); for i := 1 to la do c[la+1-i] := ord(a[i])-48; lb := length(b);

for i := 1 to lb do d[lb+1-i] := ord(b[i])-48; for j := 1 to lb do begin for i := 1 to la do e[i+j-1] := e[i+j-1]+c[i]*d[j]; for i := 1 to j+la do if e[i] > 9 then begin e[i+1] := e[i+1]+e[i] div 10; e[i] := e[i] mod 10; end; end; g := ''; for i := la+lb downto 1 do begin str(e[i],h); g := g+h; end; while (g[1] = '0') and (length(g) > 1) do delete(g,1,1); cf := g; end; begin assign(input,'product.in'); reset(input); assign(output,'product.out'); rewrite(output); readln(k); readln(s); n := length(s); for i := 1 to n do p[0,i] := copy(s,1,i); for i := 1 to k do for t := i+1 to n do begin max := '0'; for j := i to t-1 do begin s1 := cf(p[i-1,j],copy(s,j+1,t-j)); if pd(s1,max) then max := s1; end; p[i,t] := max; end; WriteLn(p[k,n]); close(input); close(output); end. 例 3-2-8 合并石子: 在一个操场上一排地摆放着N堆石子。 现要将石子有次序地合并成一堆。 规定每次只能 选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 问题求解: 试设计一个程序,计算出将N堆石子合并成一堆的最小得分。

输入文件(UNITE.IN): 第一行为一个正整数 N (2≤N≤100); 以下N行,每行一个正整数,小于 10000,分别表示第 i 堆石子的个数(1≤i≤N)。 输出文件(UNITE.OUT): 为一个正整数,即最小得分。 输入输出示例: UNITE.IN 7 13 7 8 16 21 4 18 UNITE.OUT 239 const maxn = 100; var a : array[1..maxn] of word; b : array[1..maxn,1..maxn] of longint; i,j,k,n,min : integer; begin assign(input,'unite.in'); reset(input); assign(output,'unite.out'); rewrite(output); readln(n); for i := 1 to n do readln(a[i]); fillchar(b,sizeof(b),0); for i := 2 to n do for j := 1 to n-i+1 do begin min := b[i-1,j]; for k := i-1 downto 1 do if min > b[k,j]+b[i-k,j+k] then min := b[k,j]+b[i-k,j+k]; for k := j to j+i-1 do min := min+a[k]; b[i,j] := min; end; writeln(b[n,1]); {for i := 1 to n do begin for j := 1 to n+1-i do write(b[i,j]:5); writeln;

end;} close(input); close(output); end. 例 3-2-9 高性能计算机: 现在有一项时间紧迫的工程计算任务要交给你——国家高性能并行计算机的主管工程 师——来完成。 为了尽可能充分发挥并行计算机的优势, 我们的计算任务应当划分成若干个 小的子任务。 这项大型计算任务包括 A 和 B 两个互不相关的较小的计算任务。为了充分发挥并行计 算机的运算能力,这些任务需要进行分解。研究发现,A 和 B 都可以各自划分成很多较小 的子任务,所有的 A 类子任务的工作量都是一样的,所有的 B 类子任务也是如此(A 和 B 类的子任务的工作量不一定相同) 。A 和 B 两个计算任务之间,以及各子任务之间都没有执 行顺序上的要求。 这台超级计算机拥有 p 个计算节点,每个节点都包括一个串行处理器、本地主存和高 速 cache。然而由于常年使用和不连贯的升级,各个计算节点的计算能力并不对称。一个节 点的计算能力包括如下几个方面: 1. 就本任务来说,每个节点都有三种工作状态:待机、A 类和 B 类。其中,A 类状态 下执行 A 类任务;B 类状态下执行 B 类任务;待机状态下不执行计算。所有的处 理器在开始工作之前都处于待机状态, 而从其它的状态转入 A 或 B 的工作状态 (包 括 A 和 B 之间相互转换) ,都要花费一定的启动时间。对于不同的处理节点,这个 时间不一定相同。用两个正整数 tiA 和 tiB ( i ? 1, 2,..., p )分别表示节点 i 转入工作状 2. 3. 4. 5. 6. 7. 态 A 和工作状态 B 的启动时间(单位:ns) 。 一个节点在连续处理同一类任务的时候, 执行时间——不含状态转换的时间——随 任务量(这一类子任务的数目)的平方增长,即: 若节点 i 连续处理 x 个 A 类子任务,则对应的执行时间为

t ? kiA x2
类似的,若节点 i 连续处理 x 个 B 类子任务,对应的执行时间为:

t ? kiB x2
其中, kiA 和 kiB 是系数,单位是 ns。 i ? 1, 2,..., p 。

任务分配必须在所有计算开始之前完成,所谓任务分配,即给每个计算节点设置一个 任务队列,队列由一串 A 类和 B 类子任务组成。两类子任务可以交错排列。 计算开始后,各计算节点分别从各自的子任务队列中顺序读取计算任务并执行,队列 中连续的同类子任务将由该计算节点一次性读出, 队列中一串连续的同类子任务不能被分成 两部分执行。 问题求解: 现在需要你编写程序, 给这 p 个节点安排计算任务, 使得这个工程计算任务能够尽早完 成。假定任务安排好后不再变动,而且所有的节点都同时开始运行,任务安排的目标是使最 后结束计算的节点的完成时间尽可能早。 输入文件(HPC.IN) : 输入文件的第一行是对计算任务的描述,包括两个正整数 nA 和 nB (0≤ nA 、 nB ≤60), 分别是 A 类和 B 类子任务的数目,两个整数之间由一个空格隔开。 文件的后面部分是对此计算机的描述: 文件第二行是一个整数 p(2≤p≤20) ,即计算节点的数目。 随后连续的 p 行按顺序分别描述各个节点的信息,第 i 个节点由第 i+2 行描述,该行包 括下述四个正整数(相邻两个整数之间有一个空格) :

tiA tiB kiA kiB

输出文件(HPC.OUT) : 输出文件只有一行,包含有一个正整数,即从各节点开始计算到任务完成所用的时间。 {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+} {$M 65000,0,655360} var a : array[0..60,0..60,1..2] of longint; b,c : array[0..60,0..60] of longint; na,nb,p,i,j,k,l,j1,k1 : integer; l1,l2 : longint; ta,tb,ka,kb : array[1..20] of longint; begin assign(input,'hpc.in'); reset(input); assign(output,'hpc.out'); rewrite(output); readln(na,nb); readln(p); for I := 1 to p do readln(ta[i],tb[i],ka[i],kb[i]); for I := 1 to p do begin fillchar(a,sizeof(a),0); a[0,0,1] := 0; a[0,0,2] := 0; for j := 1 to na do begin a[j,0,1] := ta[i]+ka[i]*j*j; a[j,0,2] := maxlongint end; for j := 1 to nb do begin a[0,j,2] := tb[i]+kb[i]*j*j; a[0,j,1] := maxlongint end; for j := 1 to na do for k := 1 to nb do begin a[j,k,1] := maxlongint; a[j,k,2] := maxlongint; for l := 1 to j do if a[j-l,k,2]+ta[i]+ka[i]*l*l < a[j,k,1] then a[j,k,1] := a[j-l,k,2]+ta[i]+ka[i]*l*l; for l := 1 to k do if a[j,k-l,1]+tb[i]+kb[i]*l*l < a[j,k,2] then a[j,k,2] := a[j,k-l,1]+tb[i]+kb[i]*l*l end; if I = 1 then for j := 0 to na do for k := 0 to nb do if a[j,k,1] < a[j,k,2] then c[j,k] := a[j,k,1] else c[j,k] := a[j,k,2]

else for j1 := 0 to na do for k1 := 0 to nb do begin if a[j1,k1,2] < a[j1,k1,1] then a[j1,k1,1] := a[j1,k1,2]; for j := j1 to na do for k := k1 to nb do if (c[j,k] > a[j1,k1,1]) and (c[j,k] > b[j-j1,k-k1]) then if a[j1,k1,1] < b[j-j1,k-k1] then c[j,k] := b[j-j1,k-k1] else c[j,k] := a[j1,k1,1] end; b := c end; writeln(c[na,nb]); close(input); close(output) end.

你看他写的什么无后效性什么最优子结构的就头大,我也头大%………… 动态规划一般解决两类问题,一类是最优化问题,就是问你最大价值最小数什么 的,另一类是方案总数问题。 细分的话类型很多, 我见得多的(我是高二学生,目前在筹备 NOIP) (你那题多我就只说名字了) 背包,楼上连 9 讲都放上来了我就不多说了…… 最长不上升不下降子序列问题(比如说潘帕斯雄鹰生日模拟赛的飞翔,就是很经 典的不下降的变形) 资源分配问题(比如说橱窗布置,马棚问题,机器分配问题) 区间动归(乘积最大,能量项链等等) 最长公共子序列问题(有个遗传编码好像); 解决方案树的比如说爬楼梯问题…………………… 动态规划的类型很多很多,因为他很灵活的,我们老师曾经给我们找了 100 个 DP 方程,但是那都没有用,强记根本记不住,关键是理解。 深入一点的就有 DP 的优化,时间空间的降维(就是用别的方法去做,或者比如 说背包本来是二维的空间优化过该成一维的了),树形 DP(这个我也不会)。 (优化里面有个很经典的题《过河》)

我对 DP 是属于那种突然就开了窍的……别看说“动态规划”什么的唬人,其实就 是一个比较一个计算,知道他干什么了题上来就有头绪,方程啊思想啊就有 了…… 主要也是多看题吧,从简单的开始,理解他的思想……自己写动归的时候注意下 面几个问题: 1、大前提是确定你做的是动归题……看得多了也就知道自己面对的是什么类型 的题了 2、次前提是想法要对(我做题的时候先想这道题时间空间的维度,然后根据这 个去想方程),方程正确, 实在想不起来可以先看题解,去理解人家的思想之后,不要看标程把程序做 出来…… 3、注意数组不要开的过小,一般都是左右都开大一点,比如他的数据范围是 1~100 ,数组就开 0~101.这个是防越界的,因为很多 DP 赋初值的时候会用到 F[0],F[0,0] 4、初始值要正确,因为很多 DP 其他地方都是正确的因为初始值赋错了而全部 过不了的情况是很常见的……(比如说 USACO 里面的货币系统) 5、DP 循环的范围要正确,一般根据题来判断范围写多少的(比如说橱窗问题, 今天下午写这个题因为循环写错了一直 AC 不了) USACO 里也有很多 DP 题,可以做…… 以上全部手打,希望能对你有所帮助。 我也是正在学习的人,上面的东西不一定全部正确,但是对我而言很受用,也算 是我的经验了。希望日后能一起学习交流外加进步喽 QQ:340131980 1. 资源问题 1 -----机器分配问题 F[I,j]:=max(f[i-1,k]+w[i,j-k]) 2. 资源问题 2 ------01 背包问题 F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]); 3. 线性动态规划 1 -----朴素最长非降子序列 F:=max{f[j]+1} 4. 剖分问题 1 -----石子合并 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]); 5. 剖分问题 2

-----多边形剖分 F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a); 6. 剖分问题 3 ------乘积最大 f[i,j]:=max(f[k,j-1]*mult[k,i]); 资源问题 3 -----系统可靠性(完全背包) F[i,j]:=max{f[i-1,j-c*k]*P[I,x]} 7. 8. 贪心的动态规划 1 -----快餐问题 F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2) div p3} 9. 贪心的动态规划 2 -----过河 f=min{{f(i-k)} (not stone) {f(i-k)}+1} (stone); +贪心压缩状态 10. 剖分问题 4 -----多边形-讨论的动态规划 F[i,j]:=max{正正 f[I,k]*f[k+1,j]; 负负 g[I,k]*f[k+1,j]; 正负 g[I,k]*f[k+1,j]; 负正 f[I,k]*g[k+1,j];} g 为 min 11. 树型动态规划 1 -----加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]} 12. 树型动态规划 2 -----选课 (多叉树转二叉树,自顶向下模型) F[I,j]表示以 i 为根节点选 j 门功课得到的最大学分 f[i,j]:=max{f[t.l,k]+f[t.r,j-k-1]+c} 13. 计数问题 1 -----砝码称重 f[f[0]+1]=f[j]+k*w[j]; (1<=i<=n; 1<=j<=f[0]; 1<=k<=a;) 14. 递推天地 1 ------核电站问题

f[-1]:=1; f[0]:=1; f:=2*f[i-1]-f[i-1-m] 15. 递推天地 2 ------数的划分 f[i,j]:=f[i-j,j]+f[i-1,j-1]; 16. 最大子矩阵 1 -----一最大 01 子矩阵 f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1; ans:=maxvalue(f); 17. 判定性问题 1 -----能否被 4 整除 g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false; g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j) 18. 判定性问题 2 -----能否被 k 整除 f[I,j± n mod k]:=f[i-1,j];

-k<=j<=k; 1<=i<=n

20. 线型动态规划 2 -----方块消除游戏 f[i,i-1,0]:=0 f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), f[i,p,k+len[j]]+f[p+1,j-1,0]} ans:=f[1,m,0] 21. 线型动态规划 3 -----最长公共子串,LCS 问题 f[i,j]={0(i=0)&(j=0); f[i-1,j-1]+1 (i>0,j>0,x=y[j]); max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x<>y[j]); 22. 最大子矩阵 2 -----最大带权 01 子矩阵 O(n^2*m) 枚举行的起始,压缩进数列,求最大字段和,遇 0 则清零 23. 资源问题 4 -----装箱问题(判定性 01 背包) f[j]:=(f[j] or f[j-v]);

24. 数字三角形 1 -----朴素の数字三角形 f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]); 25. 数字三角形 2 -----晴天小猪历险记之 Hill 同一阶段上暴力动态规划 if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j] 26. 双向动态规划 1 数字三角形 3 -----小胖办证 f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j]) 27. 数字三角形 4 -----过河卒 //边界初始化 f[i,j]:=f[i-1,j]+f[i,j-1]; 28. 数字三角形 5 -----朴素的打砖块 f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]); 29. 数字三角形 6 -----优化的打砖块 f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]} 30. 线性动态规划 3 -----打鼹鼠’ f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j]) 31. 树形动态规划 3 -----贪吃的九头龙

32. 状态压缩动态规划 1 -----炮兵阵地 Max(f[Q*(r+1)+k],g[j]+num[k]) If (map and plan[k]=0) and ((plan[P] or plan[q]) and plan[k]=0)

33. 递推天地 3 -----情书抄写员 f:=f[i-1]+k*f[i-2] 34. 递推天地 4 -----错位排列 f:=(i-1)(f[i-2]+f[i-1]); f[n]:=n*f[n-1]+(-1)^(n-2); 35. 递推天地 5 -----直线分平面最大区域数 f[n]:=f[n-1]+n :=n*(n+1) div 2 + 1; 36. 递推天地 6 -----折线分平面最大区域数 f[n]:=(n-1)(2*n-1)+2*n; 37. 递推天地 7 -----封闭曲线分平面最大区域数 f[n]:=f[n-1]+2*(n-1) :=sqr(n)-n+2; 38 递推天地 8 -----凸多边形分三角形方法数 f[n]:=C(2*n-2,n-1) div n; 对于 k 边形 f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3) 39 递推天地 9 -----Catalan 数列一般形式 1,1,2,5,14,42,132 f[n]:=C(2k,k) div (k+1); 40 递推天地 10 -----彩灯布置 排列组合中的环形染色问题 f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); 41 线性动态规划 4 -----找数 线性扫描 sum:=f+g[j];

(f[1]:=m; f[2]:=m(m-1);

(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);) 42 线性动态规划 5 -----隐形的翅膀 min:=min{abs(w/w[j]-gold)}; if w/w[j]<gold then inc(i) else inc(j); 43 剖分问题 5 -----最大奖励 f:=max(f,f[j]+(sum[j]-sum)*i-t 44 最短路 1 -----Floyd f[i,j]:=max(f[i,j],f[i,k]+f[k,j]); ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j]; 45 剖分问题 6 -----小 H 的小屋 F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k); 46 计数问题 2 -----陨石的秘密(排列组合中的计数问题) Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D]; F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]); 47 线性动态规划 ------合唱队形 两次 F:=max{f[j]+1}+枚举中央结点 48 资源问题 ------明明的预算方案:加花的动态规划 f[i,j]:=max(f[i,j],f[l,j-v-v[fb]-v[fa]]+v*p+v[fb]*p[fb]+v[fa]*p[fa]); 49 资源问题 -----化工场装箱员 50 树形动态规划 -----聚会的快乐 f[i,2]:=max(f[i,0],f[i,1]); f[i,1]:=sigma(f[t^.son,0]); f[i,0]:=sigma(f[t^.son,3]);

51 树形动态规划 -----皇宫看守 f[i,2]:=max(f[i,0],f[i,1]); f[i,1]:=sigma(f[t^.son,0]); f[i,0]:=sigma(f[t^.son,3]); 52 递推天地 -----盒子与球 f[i,1]:=1; f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]); 53 双重动态规划 -----有限的基因序列 f:=min{f[j]+1} g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j]) 54 最大子矩阵问题 -----居住空间 f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]), min(f[i,j,k-1],f[i-1,j-1,k])), min(min(f[i-1,j,k-1],f[i,j-1,k-1]), f[i-1,j-1,k-1]))+1; 55 线性动态规划 ------日程安排 f:=max{f[j]}+P[I]; (e[j]<s) 56 递推天地 ------组合数 C[I,j]:=C[i-1,j]+C[I-1,j-1] C[I,0]:=1 57 树形动态规划 -----有向树 k 中值问题 F[I,r,k]:=max{max{f[l,I,j]+f[r,I,k-j-1]},f[f[l,r,j]+f[r,r,k-j]+w[I,r]]} 58 树形动态规划 -----CTSC 2001 选课 F[I,j]:=w(if i∈P)+f[l,k]+f[r,m-k](0≤k≤m)(if l<>0) 59 线性动态规划 -----多重历史 f[i,j]:=sigma{f[i-k,j-1]}(if checked)

60 背包问题(+-1 背包问题+回溯) -----CEOI1998 Substract f[i,j]:=f[i-1,j-a] or f[i-1,j+a] 61 线性动态规划(字符串) -----NOI 2000 古城之谜 f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+w ords[s]} 62 线性动态规划 -----最少单词个数 f[i,j]:=max{f[I,j],f[u-1,j-1]+l} 63 线型动态规划 -----APIO2007 数据备份 状态压缩+剪掉每个阶段 j 前 j*2 个状态和 j*2+200 后的状态贪心动态规划 f:=min(g[i-2]+s,f[i-1]); 64 树形动态规划 -----APIO2007 风铃 f:=f[l]+f[r]+{1 (if c[l]<c[r])} g:=1(d[l]<>d[r]) 0(d[l]=d[r]) g[l]=g[r]=1 then Halt; 65 地图动态规划 -----NOI 2005 adv19910 F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j]; 66 地图动态规划 -----优化的 NOI 2005 adv19910 F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j; 67 目标动态规划 -----CEOI98 subtra F[I,j]:=f[I-1,j+a] or f[i-1,j-a] 68 目标动态规划 ----- Vijos 1037 搭建双塔问题 F[value,delta]:=g[value+a,delta+a] or g[value,delta-a] 69 树形动态规划

-----有线电视网 f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j]) leaves>=p>=l, 1<=q<=p; 70 地图动态规划 -----vijos 某题 F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]); 71 最大子矩阵问题 -----最大字段和问题 f:=max(f[i-1]+b,b); f[1]:=b[1] 72 最大子矩阵问题 -----最大子立方体问题 枚举一组边 i 的起始,压缩进矩阵 B[I,j]+=a[x,I,j] 枚举另外一组边的其实,做最大子矩阵 73 括号序列 -----线型动态规划 f[I,j]:=min(f[I,j],f[i+1,j-1](ss[j]=”()”or(”[]”)), f[I+1,j+1]+1 (s[j]=”(”or”[” ] , f[I,j-1]+1(s[j]=”)”or”]” ) 74 棋盘切割 -----线型动态规划 f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2], f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2] min{}} 75 概率动态规划 -----聪聪和可可(NOI2005) x:=p[p[i,j],j] f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1 f[I,i]=0 f[x,j]=1 76 概率动态规划 -----血缘关系 F[A, B]=(f[A0, B]+P[A1, B])/2 f[I,i]=1 f[I,j]=0(I,j 无相同基因) 77 线性动态规划

-----决斗 F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j 78 线性动态规划 -----舞蹈家 F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]]) 79 线性动态规划 -----积木游戏 F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’]) 80 树形动态规划(双次记录) -----NOI2003 逃学的小孩 朴素的话枚举节点 i 和离其最远的两个节点 j,k O(n^2) 每个节点记录最大的两个值,并记录这最大值分别是从哪个相邻节点传过来的。 当遍历到某个孩子节点的时候,只需检查最大值是否是从该孩子节点传递来的。 如果是,就取次大,否则取最大值 81 树形动态规划(完全二叉树) -----NOI2006 网络收费 F[I,j,k]表示在点 i 所管辖的所有用户中,有 j 个用户为 A,在 I 的每个祖先 u 上, 如果 N[a]>N 则标 0 否则标 1,用二进制状态压缩进 k 中,在这种情况下的最小 花费 F[I,j,k]:=min{f[l,u,k and (s<<(i-1))]+w1,f[r,j-u,k and(s<<(i-1))]} 82 树形动态规划 -----IOI2005 河流 F:=max 83 记忆化搜索 -----Vijos 某题,忘了 F[pre,h,m]:=sigma{SDP(I,h+1,M+i)} (pre<=i<=M+1) 84 状态压缩动态规划 -----APIO 2007 动物园 f[I,k]:=f[i-1,k and not (1<<4)] + NewAddVal 85 树形动态规划 -----访问术馆 f[i,j-c×2]:= max ( f[l,k], f[r,j-c×2-k] ) 86 字符串动态规划

-----Ural 1002 Phone if exist(copy(s,j,i-j)) then f:=min(f,f[j]+1); 87 多进程动态规划 -----CEOI 2005 service Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t] ) Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t] ) Min( f[i,j,t[i-1]], f[i-1,j,k] + c[k,t] ) 88 多进程动态规划 -----Vijos1143 三取方格数 max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]); if (j=k) and (k=l) then inc(f[i,j,k,l],a[j,i-j]) else if (j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else if (k=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else if (j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l,i-l]); 89 线型动态规划 -----IOI 2000 邮局问题 f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]); 90 线型动态规划 -----Vijos 1198 最佳课题选择 if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k)); 91 背包问题 ----- USACO Raucous Rockers 多个背包,不可以重复放物品,但放物品的顺序有限制。 F[I,j,k]表示决策到第 i 个物品、 第 j 个背包, 此背包花费了 k 的空间。 f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t]) 92 多进程动态规划 -----巡游加拿大(IOI95、USACO) d[i,j]=max{d[k,j]+1(a[k,i] & j<k<i),d[j,k]+1(a[I,j] & (k<j))}。 f[i,j]表示从起点出发, 一个人到达 i, 另一个人到达 j 时经过的城市数。 d[i,j]=d[j,i], 所以我们限制 i>j 分析状态(i,j),它可能是(k,j)(j<k<i)中 k 到达 i 得到(方式 1),也可能是(j,k)(k<j) 中 k 超过 j 到达 i 得到(方式 2)。但它不能是(i,k)(k<j)中 k 到达 j 得到,因为这 样可能会出现重复路径。即使不会出现重复路径,那么它由(j,k)通过方式 2 同样 可以得到,所以不会遗漏解 时间复杂度 O(n3)

93 动态规划 -----ZOJ cheese f[i,j]:=f[i-kk*zl[u,1],j-kk*zl[u,2]]+a[i-kk*zl[u,1],j-kk*zl[u,2]] 94 动态规划 -----NOI 2004 berry 线性 F[I,1]:=s F[I,j]:=max{min{s-s[l-1]},f[l-1,j-1]} (2≤j≤k, j≤l≤i) 95 动态规划 -----NOI 2004 berry 完全无向图 F[I,j]:=f[i-1,j] or (j≥w) and (f[i-1,j-w]) 96 动态规划 -----石子合并 四边形不等式优化 m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j] 97 动态规划 -----CEOI 2005 service (k≥long,i≥1)g[i, j, k]=max{g[i-1,j,k-long]+1,g[i-1,j,k]} (k<long,i≥1) g[i, j, k]=max{g[i-1,j-1,t-long]+1,g[i-1,j,k]} (0≤j≤m, 0≤k<t) g[0,j,k]=0; ans:=g[n,m,0]。 状态优化:g[i, j]=min{g[i-1,j],g[i-1,j-1]+long} 其中(a, b)+long=(a’, b’)的计算方法为: 当 b+long ≤t 时: a’=a; b’=b+long; 当 b+long >t 时: a’=a+1; b’=long; 规划的边界条件: 当 0≤i≤n 时,g[i,0]=(0,0) 98 动态规划 -----AHOI 2006 宝库通道 f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]} 99 动态规划 -----Travel A) 费用最少的旅行计划。 设 f 表示从起点到第 i 个旅店住宿一天的最小费用; g 表示从起点到第 i 个旅店住 宿一天,在满足最小费用的前提下所需要的最少天数。那么: f=f[x]+v, g=g[x]+1 x 满足:

1、 x<i,且 d – d[x] <= 800(一天的最大行程)。 2、 对于所有的 t < i, d – d[t] <= 800,都必须满足: A. g[x] < g[t](f[x] = f[t]时) B. f[x] < f[t] (其他情况) f[0] = 0,g[0] = 0。 Ans:=f[n + 1],g[n+1]。 B). 天数最少的旅行计划。 方法其实和第一问十分类似。 设 g’表示从起点到第 i 个旅店住宿一天的最少天数; f’表示从起点到第 i 个旅店住 宿一天,在满足最小天数前提下所需要的最少费用。那么: g’ = g’[x] + 1, f’ = f’[x] + v x 满足: 1、 x<i,且 d – d[x] <= 800(一天的最大行程)。 2、 对于所有的 t < i, d – d[t] <= 800,都必须满足: f’[x] < f’[t] g’[x] = g’[t]时 g’[x] < g’[t] 其他情况 f’[0] = 0,g’[0] = 0。 Ans:=f’[n + 1],g’[n+1]。

100 动态规划 -----NOI 2007 cash y:=f[j]/(a[j]*c[j]+b[j]); g:=c[j]*y*a+y*b; f:=max(f,g)

最小乘车费用的动规程序:


高中计算机竞赛 编程 动态规划解析辅导

高中计算机竞赛 编程 动态规划解析辅导_学科竞赛_高中教育_教育专区。第二节 动态规划 动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法...

!联赛试题分类解析之动态规划篇

!联赛试题分类解析动态规划篇_IT/计算机_专业资料。信息学,算法,编程,动态规划...高中数学竞赛(00-06年)试... 11页 免费 2013年全国中考数学试题... 149页...

高中编程竞赛1

高中编程竞赛1_IT/计算机_专业资料。高中编程竞赛1 Pascal编程 全文分为了三分,请分别下载。今日推荐 180份文档 2014证券从业资格考试 ...

动态规划习题精讲

动态规划习题精讲_数学_高中教育_教育专区。信息学竞赛...效率,但思维和编程比较简单,可以节约宝贵的竞赛时间...主件 电脑 书柜 书桌 工作椅 附件 打印机,扫描仪...

动态规划典型例题

动态规划典型例题_数学_高中教育_教育专区。初学者的必备题目 1、单调递增最长子序列描述求一个字符串的最长递增子序列的长度 如:dabdbf 最长递增子序列就是 abdf...

信息学竞赛常用的算法思想讲座之一(动态规划)

信息学竞赛常用算法思想信息学竞赛常用算法思想隐藏>> 中华IT 学习网 www.100itxx.com 官方总站:圣才学习网 www.100xuexi.com 动态规划动态规划是本书介绍的五种...

基于“信息学奥林匹克竞赛”培养程序设计习惯的研究

通过以竞赛试题中阅读程序为例,分析说明培养程序设计...以及编程技巧发展到模型设计、离散数学、动态规划的...正确掌握计算机程序设计过程,没有养成良好的程序编程...

动态规划0起点基础题目

动态规划0起点基础题目_学科竞赛_高中教育_教育专区。...若知道所有砝码的总重 量不超过 10000,请编写程序...2014教师资格材料分析辅... 2014小学教师资格考试《...

动态规划训练专题

动态规划训练专题_计算机软件及应用_IT/计算机_专业资料...佳 清华大学出版社 挑战编程:程序设计竞赛训练手册 ...2014教师资格材料分析辅... 2014小学教师资格考试《...

信息技术竞赛辅导

信息技术竞赛辅导_学科竞赛_高中教育_教育专区。信息...计算机 软件 *操作系统的使用知识 *编程语言的使用 ...化简等# *动态规划# 三、初赛试题类型:注:试题...