第1页 / 共129页
第2页 / 共129页
第3页 / 共129页
第4页 / 共129页
第5页 / 共129页
第6页 / 共129页
第7页 / 共129页
第8页 / 共129页
全面的动态规划学习资料（内附习题及详细解答）.pdf
动态规划基本原理
机器分配（HNOI’95）
最长不下降序列（HNOI’97）
凸多边形三角划分（HNOI’97）
系统可靠性（HNOI’98）
快餐问题（HNOI’99）
求函数最大值(CTSC'95)
石子合并（NOI’95）
游览街区（NOI’97）
积木游戏（NOI’97）
免费馅饼（NOI’98）
棋盘分割（NOI’99）
钉子和小球（NOI’99）
Subset（NOI’99）
陨石的秘密（NOI’2001）
商店购物（IOI’95）
最长前缀（IOI’96）
多边形（IOI’98）
花店橱窗布置（IOI’99）
选课（CTSC’98）
拯救大兵瑞恩（CTSC’99）
补丁VS错误（CSTS’99）
迷宫改造（WC’99）
奶牛浴场（WC’2002）
HPC (WC’2001)
交叉匹配 (WC’2001 练习题)
Codes (IOI‘99)
快乐的蜜月 (CTSC 2000)
Integer (HNOI 2000)
Bar
序关系计数问题 (福建试题)
Chain
Land (IOI’99)
理想收入
动态规划基本原理.......................................................................................................................1
机器分配（HNOI’95） ...............................................................................................................3
最长不下降序列（HNOI’97）....................................................................................................4
凸多边形三角划分（HNOI’97）................................................................................................6
系统可靠性（HNOI’98） ...........................................................................................................8
快餐问题（HNOI’99） ...............................................................................................................9
求函数最大值(CTSC'95) ...........................................................................................................14
石子合并（NOI’95） ................................................................................................................15
游览街区（NOI’97） ................................................................................................................17
积木游戏（NOI’97） ................................................................................................................20
免费馅饼（NOI’98） ................................................................................................................24
棋盘分割（NOI’99） ................................................................................................................27
钉子和小球（NOI’99） ............................................................................................................30
SUBSET（NOI’99）....................................................................................................................33
陨石的秘密（NOI’2001） ........................................................................................................38
商店购物（IOI’95）..................................................................................................................42
最长前缀（IOI’96）..................................................................................................................48
多边形（IOI’98）......................................................................................................................52
花店橱窗布置（IOI’99）..........................................................................................................56
选课（CTSC’98） .....................................................................................................................59
拯救大兵瑞恩（CTSC’99） .....................................................................................................63
补丁 VS 错误（CSTS’99）.......................................................................................................69
迷宫改造（WC’99）.................................................................................................................72
奶牛浴场（WC’2002）.............................................................................................................80
HPC (WC’2001)..........................................................................................................................85
交叉匹配 (WC’2001 练习题) ...................................................................................................90
CODES (IOI‘99) ...........................................................................................................................93
快乐的蜜月 (CTSC 2000)......................................................................................................102
INTEGER (HNOI 2000) ..............................................................................................................108
BAR ...........................................................................................................................................110
序关系计数问题 (福建试题)...................................................................................................113
CHAIN........................................................................................................................................116
LAND (IOI’99)...........................................................................................................................119
理想收入...................................................................................................................................125
0
动态规划基本原理
近年来，涉及动态规划的各种竞赛题越来越多，每一年的 NOI 几乎都至少有一道题目需
要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再
停留于简单的递推和建模上了。
要了解动态规划的概念，首先要知道什么是多阶段决策问题。
一、多阶段决策问题
如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取
措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个
过程的活动路线，则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选
择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用
数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，
选取一个最优策略，使在预定的标准下达到最好的效果.
让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从 A到 D的最短
路径的长度(下面简称最短距离)。
图 4-1 带权有向多段图
我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可能
尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，A点要到达 D点必然
要经过 B1和 B2中的一个，所以 A到 D的最短距离必然等于 B1到 D的最短距离加上 5，或
是 B2到 D的最短距离加上 2。同样的，B1到 D的最短距离必然等于 C1到 D的最短距离加上
3或是 C2到 D的最短距离加上 2，……。
我们设 G[i]为点 i到点 D的距离，显然 G[C1]=4，G[C2]=3，G[C3]=5，根据上面的分析，
有：
G[B1]=min{G[C1]+3，G[C2]+2}=5，
G[B2]=min{G[C2]+7，G[C3]+4}=9，
再就有 G[A]=min{G[B1]+5，G[B2]+2}=10，
所以 A到 D的最短距离是 10，最短路径是 AB1C2D。
二、动态规划的术语
1．阶段
1
把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶
段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用 k
表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两
个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。
在前面的例子中，第一个阶段就是点 A，而第二个阶段就是点 A到点 B，第三个阶段是
点 B到点 C，而第四个阶段是点 C到点 D。
2．状态
状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也
称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，
同时又是前一阶段某支路的终点。
在前面的例子中，第一个阶段有一个状态即 A，而第二个阶段有两个状态 B1 和 B2，第
三个阶段是三个状态 C1，C2 和 C3，而第四个阶段又是一个状态 D。
过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但
有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状
态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状
态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。
当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取
值。状态变量取值的集合称为状态集合。
3．无后效性
我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发
展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，
过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始
点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的
始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能
通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
4．决策
一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为
决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一
组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，
故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
决策变量的范围称为允许决策集合。
5．策略
由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取
的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策
略称为最优策略。
给定 k阶段状态变量 x(k)的值后，如果这一阶段的决策变量一经确定，第 k+1阶段的
状态变量 x(k+1)也就完全确定，即 x(k+1)的值随 x(k)和第 k阶段的决策 u(k)的值变化而变
化 ， 那 么 可 以 把 这 一 关 系 看 成 (x(k)， u(k))与 x(k+1)确 定 的 对 应 关 系 ， 用
x(k+1)=Tk(x(k),u(k))表示。这是从 k阶段到 k+1阶段的状态转移规律，称为状态转移方程。
6．最优性原理
2
作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必
然构成“最优子策略”。
最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分
析来具体说明这一点：从 A 到 D，我们知道，最短路径是 AB1C2D，这些点的选择
构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：AB1C2
是 A 到 C2 的最短路径，B1C2D 也是 B1 到 D 的最短路径……事实正是如此，因此我们
认为这个例子满足最优性原理的要求。
下面我们列举历年国内国际竞赛的一些典型动态规划问题加以分析。
机器分配（HNOI’95）
一、问题描述
总公司拥有高效生产设备 M 台，准备分给下属的 N 个公司。各分公司若获得这些设备，
可以为国家提供一定的盈利。问：如何分配这 M 台设备才能使国家得到的盈利最大？求出
最大盈利值。其中 M《=15，N〈=10。分配原则：每个公司有权获得任意数目的设备，但总
台数不得超过总设备数 M。保存数据的文件名从键盘输入。
数据文件格式为：第一行保存两个数，第一个数是设备台数 M，第二个数是分公司数 N。
接下来是一个 M*N 的矩阵，表明了第 I 个公司分配 J 台机器的盈利。
二、分析
这是一个典型的动态规划试题。用机器数来做状态，数组 F[I，J]表示前 I 个公司分配
J 台机器的最大盈利。则状态转移方程为
F[I，J]=Max{F[I-1，K] + Value[I，J-K]} （0〈=K〈=J〉
三、参考程序：
program hnoi_95_4;
var
a , b , c : array[0..15,0..15] of longint;
d : array[0..15] of longint;
n , m : longint;
procedure init;
var
fi : text;
I , j , k : integer;
Begin
Assign(fi,’input.txt’); Reset(fi);
Readln(fi,m,n);
For I:= 0 to m do
Begin
Read(fi,j);
For k := 1 to n do
Read(fi,a[k,I]);
Readln(fi);
End;
3
Close(fi);
End;
Procedure dynamic;
Var I , j , k : longint;
Begin
For I := 1 to n do
End;
Writeln(fo,b[n,m]);
For j := 0 to m do
For k := 0 to j do
If b[I-1,k] + a[I,j-k] > b[I,j] then begin
B[I,j] := b[I-1,k] + a[I,j-k];
End;
Begin
Init;
Dynamic;
End.
一、问题描述
最长不下降序列（HNOI’97）
设有整数序列 b1,b2,b3,…,bm，若存在 i1bj )，那么前 I 个数
中最大不下降序列便是前 j 个数中最大不下降序列后添加 bi 而得。可见此任务满足最优子结
构，可以用动态规划解决。
通过上面的分析可得状态转移方程如下：
F(i)=max{F(j)+1}(j
1 2 2
这样一个序列，最大不下降序列长度为 2。但如果按上述方法计算序列 1 2 会算两次。
因此，我们对算法进行改进：
对原序列按 b 从小到大（当 bi=bj 时按 F 从大到小）排序，增设 Order(i)记录新序列
中的 I 个数在原序列中的位置。可见，当求 Total(i)时，当 F(j)=F(j+1) , b(j)=b(j+1)且
Order(j+1)b[j])and(f[i]len then len:=f[i] {记录最大值}
end;
5
for i:=1 to n do order[i]:=i;
for i:=1 to n do {排序}
for j:=i+1 to n do
if (b[i]>b[j])or(b[i]=b[j])and(f[i]>f[j]) then begin
t:=b[i];b[i]:=b[j];b[j]:=t;
t:=f[i];f[i]:=f[j];f[j]:=t;
t:=order[i];order[i]:=order[j];order[j]:=t
end;
tot:=0; {计算序列个数}
fillchar(total,sizeof(total),0);
for i:=1 to n do begin
if f[i]=1 then total[i]:=1
else
for j:=i-1 downto 1 do
if (f[j]=f[i]-1)and(b[j]b[j])or(f[j+1]<>f[j])or(order[j+1]>=order[i]) then
inc(total[i],total[j]);
if (f[i]=len)and(b[i]<>b[i+1]) then {记录累加最终值}
tot:=tot+total[i]
end;
end;
Procedure out; {输出}
begin
assign(output,fout);rewrite(output);
writeln(len);
writeln(tot);
close(output)
end;
Begin
init;
main;
out
End.
凸多边形三角划分（HNOI’97）
一、试题描述
给定一个具有 N（N<50）个顶点（从 1到 N编号）的凸多边形，每个顶点的权均已知。
问如何把这个凸多边形划分成 N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之
和最小？
输入文件：第一行 顶点数 N
第二行 N个顶点（从 1到 N）的权值
6
输出格式：最小的和的值
各三角形组成的方式
输入示例：5
122 123 245 231
输出示例：The minimum is ：12214884
The formation of 3 triangle:
3 4 5, 1 5 3, 1 2 3
二、试题分析
这是一道很典型的动态规划问题。设 F[I,J]（IF[I,K]+F[K,J]+S[I]*S[J]*S[K]) Then
Begin
F[I,J]:=F[I,K]+F[K,J]+S[I]*S[J]*S[K];
D[I,J]:=K; （记录父节点）
End;
End;
Procedure Print(I,J:Integer); （输出每个三角形）
7
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
