动态规划速成攻略.docx
《动态规划速成攻略.docx》由会员分享，可在线阅读，更多相关《动态规划速成攻略.docx（8页珍藏版）》请在冰点文库上搜索。
动态规划速成攻略
动态规划速成攻略之马矢奏春创作
创作时间：
贰零贰壹年柒月贰叁拾日
福建泉州一中倪永毅
在全国NOIP复赛中，几乎每年都会出现用动态规划思想来解决的题目，复赛中能否取得好成绩，关键就是看动态规划掌握的情况。
那对于从高中入学才开始编程语言的学生来说，有没有一种方法能速成动态规划呢？
自己经过几年的信息学奥赛辅导，通过对动态规划试题进行归纳、总结、优化等方面的研究，在这里浅谈下动态规划的速成攻略，缺乏之处请大家见谅。
一、精练动态规划经典试题
动态规划的试题有很多，学生刚开始学习时，一定要精挑细选，让学生做些动态规划入门的题目，这一阶段练习目的主要是让学生掌握好动态规划的一些基本概念，比方阶段、状态、决策、状态转移方程、无后效性、最优性原理等概念。
这些题目有：
数字三角形（IOI1994）、拦截导弹（NOIP1999）、合唱队形（NOIP2004）、挖地雷（NOIP1996）
二、对动态规划类试题进行分类教学
我们把动态规划的试题依照罕见的模型把它分类，然后让学生来分类掌握，触类旁通，事半功倍。
罕见的动态规划可以划分以下几类：
1、线性类动态规划：
典型题目：
数字三角形（IOI1994）、拦截导弹（NOIP1999）、合唱队形（NOIP2004），马拦过河卒（NOIP2002），免费馅饼（NOI’98），商店购物（IOI’95）等
2、合并类动态规划：
典型题目：
石子合并（NOI’95），乘积最大（NOIP2000），能量项链（NOIP2006）、数字游戏（NOIP2003）、添括号问题（NOI'96）等
3、背包类动态规划：
它包含0/1背包、完全背包、有限背包、有依赖的背包等背包问题是极为经典的模型，其转化与优化也是很重要的。
（详细可参考DDengi写的《背包九讲》）
典型题目：
开心的金明（NOIP2006）、采药（NOIP2005）、装箱问题（NOIP2001）、金明的预算方案（noip2006）等
4、多线程类动态规划：
典型题目：
三取方格数（noip2000）、传纸条（noip2008）、巡游加拿大（IOI95）等
5、最大子段和模型
联赛还未考到这种模型，其实它也是经典利用动态规划来解决的问题之一。
问题原型为求数组中的子数组之和的最大值。
用ans[i]暗示包含数列第i项的前i个元素的最大和，数组no存放数列元素，则状态转移方程为：
ans[0]=0；
ans[i]=max{ans[i-1]+no[i],no[i]}时间复杂度为O（n）
核心程序代码：
best:
=-maxlongint;
temp:
=0;
fori:
=1tondo
begin
inc（temp,no[i]）;
iftemp>bestthenbest:
=temp;
iftemp<0thentemp:
=0;
end;
它的一维改版有：
求K大子段和、游览街区（NOI’97），最大子矩阵和等。
二维的有：
条件约束的最大子矩阵和奶牛浴场（WC’2002）等题目
6、游戏模型
这类题的阶段（一般是时间）和决策（一般就是游戏目标）很清楚，因此比较容易想到。
典型题目：
免费馅饼（NOI98）、HelpJimmy（CEOI2000）、瑰丽华尔兹（NOI2005，优化需要多费功夫）、矩阵取数游戏（NOIP2007）。
7、其他模型：
包含树型、状态压缩类过河、资源分配类、多次动态规划等模型
典型题目有：
树网的核（NOIP2007），加分二叉树（NOIP2003）、过河（NOIP2005）、机器分配（HNOI’95）等
在教学过程中，一般每种模型只讲1-2道题目或者甚至不讲，主要是把任务分解、安插好让学生自己独立完成，培养学生的自学能力。
学生自己解决不了的就找人讨论，到各个论坛上提问，看解题陈述等方法，最后才找老师。
三、提倡“一题多变”和“一题多解”，提高学生的解题能力
动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质分歧，确定最优解的条件也互不相同，因而动态规划的设计方法对分歧的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。
所以平时训练时，其实不提倡题海战术，我们可以通过对经典试题的条件加以变更，形成“一题多变”和“一题多解”来培养学生分析问题、解决问题能力。
例：
数的计数（NOIP2001）
【描述】
我们要求找出具有下列性质数的个数（包含输入的自然数n）:
先输入一个自然数n（n≤1000），然后对此自然数依照如下方法进行处理
（1）不作任何处理:
（2）它的左边加上一个自然数，但该自然数不克不及超出原数的一半;
（3）加上数后，继续按此规则进行处理，直到不克不及再而自然数为止。
输入：
6
满足条件的数为6（此部分不必输出）
16
26
126
36
136
输出：
6
【分析】对大部分学生来讲会直接采取递归算法来求解。
代码如下
varn,i,k:
longint;
proceduresol（x:
longint）;
vari:
longint;
begin
inc（k）;
fori:
=1toxdiv2do
sol（i）;
end;
begin
readln（n）;
k:
=0;
sol（n）;
end.
如果把条件n<=1000改为n<=10000，这时候必须采取动态规划（递推）算法来完成。
用f[n]暗示最后一个数是n时，可以构造出的数的总数。
规定f[0]=1，则显然有f[n]=f[0]+f[1]+...+f[ndiv2]。
代码如下：
vari,j,s,n:
longint;
f:
array[1..1000]oflongint;
begin
read（n）;
fori:
=1tondof[i]:
=1;
f[i]:
=1;
fori:
=2tondo
forj:
=1toidiv2do
inc（f[i],f[j]）;
writeln（f[n]）;
end.
如果把条件n<=1000改为n<=3000000， 然后直接使用递推方程，则会既TLE（超时）又MLE（超空间）。
注意到右边其实是f数组开头若干个元素的和，因此可开一个s数组，用s[n]来存储f[0]至f[ndiv2]的和。
实际上，现在f数组已经不需要了，因为用s数组可写出如下状态转移方程：
s[n]=s[n-1]+s[ndiv2]（n为偶数时）或s[n]=s[n-1]（n为奇数时）。
当读入n时，输出s[ndiv2]即可。
但是这只解决了TLE的问题，MLE的问题就要考虑再加上用高精度来解决。
可以用3个int64来存储一个数。
这里我们看到用s数组代替f数组同样解决了MLE的问题，因为s数组的大小只有f数组的一半，题目允许的内存不克不及容纳f数组，却恰好可以容纳s数组。
代码如下：
const
Max=1000000000;
D=1500000;
type
xNumber=array[0..6]ofLongint;
var
i,j,n:
Longint;
f:
array[0..D]ofxNumber;
x:
xNumber;
t:
string;
begin
FillChar（f,SizeOf（f）,0）;
f[0,0]:
=1;
f[0,1]:
=1;
fori:
=1toDdobegin
f[i]:
=f[i-1];
ifnotOdd（i）thenbegin
forj:
=1tof[i,0]dobegin
Inc（f[i,j],f[idiv2,j]）;
iff[i,j]>=Maxthenbegin
Dec（f[i,j],Max）;
Inc（f[i,j+1],1）;
end;
iff[i,f[i,0]+1]>0thenInc（f[i,0]）;
end;
end;
end;
begin
Readln（n）;
ifn<=Dthenbegin
Write（f[n,f[n,0]]）;
fori:
=f[n,0]-1downto1dobegin
Str（f[n,i],t）;
forj:
=1to9-Length（t）doWrite（0）;
Write（t）;
end;
Writeln;
end
elsebegin
FillChar（x,SizeOf（x）,0）;
x[0]:
=1;
fori:
=0tondiv2dobegin
forj:
=1tox[0]dobegin
Inc（x[j],f[i,j]）;
ifx[j]>=Maxthenbegin
Dec（x[j],Max）;
Inc（x[j+1],1）;
end;
if（x[0]+1<7）and（x[x[0]+1]>0）thenInc（x[0]）;
end;
end;
Write（x[x[0]]）;
fori:
=x[0]-1downto1dobegin
Str（x[i],t）;
forj:
=1to9-Length（t）doWrite（0）;
Write（t）;
end;
Writeln;
end;
end;
end.
当然这道题还可以变更为：
对折集问题
问题描述
给定一个自然数n，由n开始可以依次发生对折集set（n）中的数如下。
（1）n∈set（n）；
（2）在n的左边加上一个自然数，但该自然数不克不及超出最近添加的数的一半；
（3）按此规则进行处理，直到不克不及再添加自然数为止。
例如，set（6）={6,16,26,126,36,136}。
对折集set（6）中有6个元素。
注意对折集不是多重集。
集合中已经有的元素不再添加到集合中。
编程任务：
对于给定的自然数n，编程计算对折集set（n）中的元素个数。
（0【分析】这是福建2005年省选题，当时很多同学都做了，可是结果都WA了。
为什么呢？
其实他们都当成“数的计数”问题来解决了。
其实是纷歧样的，比方当N=24的时候可以在24前面加个12组成1224，也可以在24前面加2再加1组成1224，“对折集”把上述两种得出1224的情况当成是同一种情况，但“数的计数”是统计成两种情况。
所以这道题真正的方法是采取枚举+HASH判重或者递推+局部限制。
“一题多变”和“一题多解”不单拓展了学生的解题思路、解题手段，而且能提高学生的编程能力，使学生能在联赛中做到“以不变应万变”。
本文探讨至此，希望对你有所启发。
从迷茫走过来的笔者，深知掌握动态规划对于刚踏上信息学竞赛辅导之路的同行来说是一件艰难的事，借此机会，笔者将自己的一些想法和大家交流一下，与大家共勉，也希望能够给介入信息学竞赛的学生一点帮忙。
创作时间：
贰零贰壹年柒月贰叁拾日
升级会员 