动态规划 入门 二
第二节 动态规划分类讨论这里用状态维数对动态规划进行了分类：
1.状态是一维的
1．1下降/非降子序列问题：
问题描述：{挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解}
在一个无序的序列a1,a2,a3,a4…an里，找到一个最长的序列满足：ai<=aj<=ak…<=am,且i<j<k…<m.（最长非降子序列）或ai>aj>ak…>am,且i>j>k…>m.（最长下降子序列）。
问题分析：
如果前i-1个数中用到ak (ak>ai或ak<=ai)构成了一个的最长的序列加上第I个数ai就是前i个数中用到i的最长的序列了。那么求用到ak构成的最长的序列有要求前k-1个数中……
从上面的分析可以看出这样划分问题满足最优子结构，那满足无后效性么？显然对于第i个数时只考虑前i-1个数,显然满足无后效性，可以用动态规划解。
分析到这里动态规划的三要素就不难得出了：如果按照序列编号划分阶段，设计一个状态opt 表示前i个数中用到第i个数所构成的最优解。那么决策就是在前i-1个状态中找到最大的opt使得aj>ai(或aj<=ai)，opt+1就是opt的值；用方程表示为：{我习惯了这种写法，但不是状态转移方程的标准写法 }
opt=max(opt)+1 (0<=j<i 且aj<=ai) {最长上升序列}
opt=max(opt)+1 (0<=j<i 且aj>ai) {最长下降序列}
实现求解的部分代码：
opt:=maxsize；{maxsize 为maxlongint或-maxlongint}
fori:=1 to n do
for j:=0 to i-1 do
if ( a>a) and (opt+1>opt) then
opt:=opt+1;
ans:=-maxlongint;
for i:=1 to n do
if opt>ans then ans:=opt; {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可以拦截最多能拦截到的导弹的个数。
状态转移方程：
opt=max(opt)+1(h>=h,0=<j<i) {h存，第i个导弹的高度}
最大的opt就是最终的解。
这只解决了第一问，对于第二问最直观的方法就是求完一次opt后把刚才要打的导弹去掉，在求一次opt直到打完所有的导弹，但这样做就错了。
不难举出反例： 6 1 7 3 2
错解： 6 3 2/1/7 正解：6 1/7 3 2
其实认真分析一下题就回发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，经过这么一分析，这个问题便抽象成在已知序列里找最长上升序列的问题。
求最长上升序列和上面说的求最长非升序列是一样的，这里就不多说了。
复杂度：时间复杂度为O（N2），空间复杂度为O（N）。
C++代码
#include<iostream> using namespace std; int shu; int fj; int fup; int n; int main() { n=0; int maxa=-564;int maxb=-21321; for(int i=1;i<=5000;i++) { fj=1; fup=1; } cin>>n; for(int i=1;i<=n;i++) cin>>shu; for(int i=2;i<=n;i++) { for(int j=i-1;j>=1;j--) { if(shu<=shu) { if( fj<fj+1) fj=fj+1; } } if(fj>maxa) maxa=fj; } for(int i=2;i<=n;i++) { for(int j=i-1;j>=1;j--) { if(shu>=shu) { if(fup<fup+1) fup=fup+1; } } if(fup>maxb) maxb=fup; } cout<<maxa<<" "<<maxb; return 0; }
转自：http://stumble41.com/article.asp?id=60
页:
[1]