动态规划速成攻略

1、动态规划速成攻略福建泉州一中倪永毅在全国NOIP复赛中，几乎每年都会出现用动态规划思想来解决的题目，复赛中能否取得 好成绩，关键就是看动态规划掌握的情况。那对于从髙中入学才开始编程语言的学生来说， 有没有一种方法能速成动态规划呢？本人经过几年的信息学奥赛辅导，通过对动态规划试题 进行归纳、总结、优化等方而的研究，在这里浅谈下动态规划的速成攻略，不足之处请大家 见谅。一、精练动态规划经典试题动态规划的试题有很多，学生刚开始学习时，一疋要精挑细选，让学生做些动态规划入 门的题目，这一阶段练习目的主要是让学生掌握好动态规划的一些基本概念，比如阶段、状 态、决策、状态转移方程、无后效性、最优性原理等概

2、念。这些题目有：数字三角形(IOI1994).拦截导弹(NOIP1999).合唱队形(NOIP2004). 挖地雷(NOIP1996 )二、对动态规划类试题进行分类教学我们把动态规划的试题按照常见的模型把它分类，然后让学生来分类掌握，触类旁通， 事半功倍。常见的动态规划可以划分以下几类：1、线性类动态规划：典型题目：数字三角形(IOI1994).拦截导弹(NOIP1999).合唱队形(NOIP2004), 马拦过河卒(NOIP2002),免费馅饼(NOV 98),商店购物(IOF 95)等2、合并类动态规划：典型题目：石子合并(NOI' 95),乘积最大(NOIP2000),能量项链(

3、NOIP2006)、数字游戏 (NOIP2003).添括号问题(NOI96)等3、背包类动态规划：它包括0/1背包、完全背包、有限背包、有依赖的背包等背包问题是极为经典的模型，其 转化与优化也是很重要的。(详细可参考DD engi写的背包九讲)典型题目：开心的金明(NOIP2006)、采药(NOIP2005)、装箱问题(NOIP2001)、金明的预 算方案(noip2006)等4、多线程类动态规划：典型题目：三取方格数(noip2000)、传纸条(noip2008)、巡游加拿大(IOI95)等5、最大子段和模型联赛还未考到这种模型，其实它也是经典利用动态规划来解决的问题之一。问题原型为求 数组

4、中的子数组之和的最大值用ansi表示包含数列第i项的前i个元素的最大和，数组no存放数列元素，则状态转移 方程为：ans0=0：ansi=max ansi-l+noi,noi时间复杂度为 O(n)核心程序代码：best:=-maxlongint:temp:=0;for i:=l to n dobegininc(temp,noi);if temp>best then best:=temp;if temp<0 then temp:=O;end;它的一维改版有：求K大子段和、游览街区（NOI' 97）,最大子矩阵和等。二维的有：条件 约束的最大子矩阵和奶牛浴场（WC，2002）等

5、题目6、游戏模型这类题的阶段（一般是时间）和决策（一般就是游戏目标）很淸楚，因此比较容易想到。 典型题目:免费馅饼（NOI98人Help Jimmy （CEOI2000）.瑰丽华尔兹（NOI2005,优化需要 多费功夫）、矩阵取数游戏（NOIP2007）。7、其他模型：包括树型、状态压缩类过河、资源分配类、多次动态规划等模型典型题目有：树网的核（NOIP2007）,加分二叉树（NOIP2003）.过河（NOIP2005）.机器分 配（HNOI' 95）等在教学过程中，一般每种模型只讲12道题目或者甚至不讲，主要是把任务分解、布置 好让学生自己独立完成，培养学生的自学能力。学生自己解决不

6、了的就找人讨论，到各个论 坛上提问，看解题报告等方法，最后才找老师。三. 提倡“一题多变”和“一题多解S提髙学生的解题能力动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确左最优解 的条件也互不相同，因而动态规划的设il方法对不同的问题，有各具特色的解题方法，而不 存在一种万能的动态规划算法，可以解决各类最优化问题。所以平时训练时，并不提倡题海 战术，我们可以通过对经典试题的条件加以变化，形成“一题多变”和“一题多解”来培养 学生分析问题、解决问题能力。例：数的计数（NOIP2001）【描述】我们要求找岀具有下列性质数的个数（包含输入的自然数n）： 先输入一个自然数n（nl0

7、00）,然后对此自然数按照如下方法进行处理（1）不作任何处理：（2）它的左边加上一个自然数，但该自然数不能超过原数的一半；（3）加上数后.继续按此规则进行处理，直到不能再而自然数为止。输入：6满足条件的数为6（此部分不必输出）162612636136输岀：6【分析】对大部分学生来讲会直接采用递归算法来求解。代码如下var nj,k:longint;procedure sol（x:longint）;var i:longint;begininc（k）;for i:=l to x div 2 dosol（i）;end;beginreadln（n）;k:=0;sol（n）;end.如果把条件n<

8、=1000改为n<=10000,这时候必须采用动态规划(递推)算法来完成。用fn 表示最后一个数是n时，可以构适出的数的总数。规泄f0 = l ,则显然有 fn=f0+fl+.+fn div 2代码如下:var ij,s,n:longint;f: array 1 .JOOOJof longint;beginread(n);for i:=l to n do fi:=l;for i:=2 to n dofor j:=l to i div 2 doinc(fli,flj);writeln(fn);end.如果把条件n<=1000改为n<=3000000, 然后直接使用递推方程，则会

9、既TLE (超时) 又MLE (超空间注意到右边其实是f数组开头若干个元素的和，因此可开一个s数组，用 sn来存储f0至fn div 2的和。实际上，现在f数组已经不必要了，因为用s数组可写 出如下状态转移方程：sn =sn-l+sn div 2(n为偶数时)或sn =sn-l(n为奇数 时)。当读入n时，输出sn div 2即可。但是这只解决了 TLE的问题，MLE的问题就要考 虑再加上用髙精度来解决。可以用3个int64来存储一个数。这里我们看到用s数组代替f 数组同样解决了 MLE的问题，因为s数组的大小只有f数组的一半，题目允许的内存不能容 纳f数组，却恰好可以容纳s数组。代码如下：c

10、onstMax= 1000000000;D= 1500000:typexNumber=array0.6 of Longint;varijji:Longint;f:array0.D of xNumber;x:xNumber;t:string;beginFillChar(f.SizeOf(f),0);f0,0:=l;f0J:=l;for i:=l to D do beginif not Odd(i) then beginfor j:=l to fi,0 do beginInc(fi,j,fi div 2JJ);if fij>=Max then beginDec(fi,j,Max);Inc(f

11、i,j+l,l);end;if fi,fi,0+l>0 then Inc(fi,O);end;end;end;beginReadln(n);if n<=D then beginWrite(fn,fn.O);for i:=fn.0-l downto 1 do beginStr(fna,t);for j:=l to 9-Length(t) do Write(O);Write(t);end;Writein;endelse beginFillChar(x.SizeOf(x),0);x0:=l;for i:=0 to n div 2 do beginfor j:=l to x0 do beg

12、in Inc(xj,fi,j); if x(j>=Max then beginDec(xj,Max);Inc(x|j+l,l);end;if (x0+l<7) and (xx0+l>0) then Inc(xO);end;end;Write(xx0);for i:=x0-l downto 1 do beginStr(xi,t);for j:=l to 9-Length(t) do Write(O);Write(t);end;Writein;end;end;end.当然这道题还可以变化为：半数集问题问题描述给左一个自然数m由n开始可以依次产生半数集set(n)中的数如下。(1)

13、 n eset(n)：(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3) 按此规则进行处理，直到不能再添加自然数为止。例如，set(6)=6,16z26,126,36,136.半数集 set中有 6 个元素。 注意半数集不是多重集。集合中已经有的元素不再添加到集合中。编程任务：对于给左的自然数n，编程汁算半数集set(n)中的元素个数匚(0<n<201)【分析】这是福建2005年省选题，当时很多同学都做了，可是结果都WAT。为什么呢？其 实他们都当成“数的讣数”问题来解决了。其实是不一样的，比如当N=24的时候可以在24 前而加个12组成1224,也可以在24前而加2再加1组成1224, “半数集”把上述两种得出 1224的情况当成是同一种情况，但“数的计数"是统计成两种情况。所