动态规划超级详细的讲义.doc

动态规划入门1(2008-09-20 21:40:51) 第二节 动态规划分类讨论 这里用状态维数对动态规划进行了分类： ?1.状态是一维的 1．1下降/非降子序列问题： 问题描述：? {挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解} 在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：ai=aj=ak…=am,且ijk…m.（最长非降子序列）或aiajak…am,且ijk…m.（最长下降子序列）。 问题分析： 如果前i-1个数中用到ak (akai或ak=ai)构成了一个的最长的序列加上第I个数ai就是前i个数中用到i的最长的序列了。那么求用到ak构成的最长的序列有要求前k-1个数中…… 从上面的分析可以看出这样划分问题满足最优子结构，那满足无后效性么？显然对于第i个数时只考虑前i-1个数,显然满足无后效性，可以用动态规划解。 分析到这里动态规划的三要素就不难得出了：如果按照序列编号划分阶段，设计一个状态opt[i] 表示前i个数中用到第i个数所构成的最优解。那么决策就是在前i-1个状态中找到最大的opt[j]使得ajai(或aj=ai)，opt[j]+1就是opt[i]的值；用方程表示为：{我习惯了这种写法，但不是状态转移方程的标准写法 } opt[i]=max(opt[j])+1?? (0=ji 且aj=ai)?????? {最长非降子序列} opt[i]=max(opt[j])+1?? (0=ji 且ajai)??????? {最长下降子序列} 实现求解的部分代码： ????? 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]+1opt[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 【问题分析】 有经验的选手不难看出这是一个求最长非升子序列问题，显然标准算法是动态规划。 以导弹依次飞来的顺序为阶段，设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。 状态转移方程： opt[i]=max(opt[j])+1? (h[i]=h[j],0=ji)?? {h[i]存，第i个导弹的高度} 最大的opt[i]就是最终的解。 这只解决了第一问，对于第二问最直观的方法就是求完一次opt[i]后把刚才要打的导弹去掉，在求一次opt[i]直到打完所有的导弹，但这样做就错了。 不难举出反例： 6 1 7 3 2??????? 错解： 6 3 2/1/7?? 正解：6 1/7 3 2 其实认真分析一下题就回发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题。 求最长上升序列和上面说的求最长非升序列是一样的，这里就不多说了。 复杂度：时间复杂度为O（N2），空间复杂度为O（N）。 【源代码】 program missile; const ?fin=missile.in; 爁out=missile.out; 爉axn=10000; var 燼