第二节 动态规划分类讨论
这里用状态维数对动态规划进行了分类:
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个数所构成的最优解。那么决策就是在前i-1个状态中找到最大的opt[j]使得aj>ai(或aj<=ai),opt[j]+1就是opt[i]的值;用方程表示为:{我习惯了这种写法,但不是状态转移方程的标准写法 }
opt[i]=max(opt[j])+1 (0<=j<i 且aj<=ai) {最长上升序列}
opt[i]=max(opt[j])+1 (0<=j<i 且aj>ai) {最长下降序列}
实现求解的部分代码:
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]+1>opt[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=<j<i) {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)。
C++代码
#include<iostream>
using namespace std;
int shu[5001];
int fj[5001];
int fup[5001];
int n;
int main()
{
n=0;
int maxa=-564;int maxb=-21321;
for(int i=1;i<=5000;i++)
{
fj[i]=1;
fup[i]=1;
}
cin>>n;
for(int i=1;i<=n;i++)
cin>>shu[i];
for(int i=2;i<=n;i++)
{
for(int j=i-1;j>=1;j--)
{
if(shu[i]<=shu[j])
{
if( fj[i]<fj[j]+1)
fj[i]=fj[j]+1;
}
}
if(fj[i]>maxa)
maxa=fj[i];
}
for(int i=2;i<=n;i++)
{
for(int j=i-1;j>=1;j--)
{
if(shu[i]>=shu[j])
{
if(fup[i]<fup[j]+1)
fup[i]=fup[j]+1;
}
}
if(fup[i]>maxb)
maxb=fup[i];
}
cout<<maxa<<" "<<maxb;
return 0;
}
转自:http://stumble41.com/article.asp?id=60
分享到:
相关推荐
很好的动态规划的资料。 一共有32讲,并且有动态规划状态转移方程的总结。 第一节 动态规划基本概念 第二节 动态规划分类讨论 动态规划入门3 动态规划入门4 动态规划入门5 动态规划入门6 ...动态规划入门8……
在一个加油站加油时,司机要花费2元买东西吃;司机不必为其他意外情况而准备额外的油;汽车开出时在起点加满油箱;计算精确到分(1元=100分)。编写程序估计实际行驶在某路线所需的最小费用。 输入格式: 从当前目录...
C++动态规划实现01背包算法入门通过二维表的方式实现01背包的选取问题
ACM 程序设计竞赛入门:第9讲 动态规划(2).ppt
1、了解什么是动态规划 2、斐波那契、爬楼梯、跳台阶等入门动态规划思想详细讲解 3、LCS、LIS等经典动态规划问题详解 4、打家劫舍系列问题分析 5、买卖股票最佳时间问题分析
算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于HTML的分治和动态规划源码.zip算法课OJ作业-基于...
动态规划本来就很抽象,状态的设定和状态的转移都不好把握,而状态压缩的动态规划解决的就是那种状态很多,不容易用一般的方法表示的动态规划问题,这个就更加的难于把握了。难点在于以下几个方面:状态怎么压缩?...
算法分析与设计实验-基于Vue3和Typescript实现的排序、动态规划、贪心算法、检索源码.zip算法分析与设计实验-基于Vue3和Typescript实现的排序、动态规划、贪心算法、检索源码.zip算法分析与设计实验-基于Vue3和...
基于多种常见算法实现动态规划项目c++源码+详细注释(回溯、贪心、递归、分支限界、分治等算法).zip基于多种常见算法实现动态规划项目c++源码+详细注释(回溯、贪心、递归、分支限界、分治等算法).zip基于多种常见算法...
《算法设计与分析》课程笔记代码Part2(动态规划+贪心算法+回溯算法) 本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支...
毕业设计基于深度强化学习的双目标动态感知路径规划python源码.zip毕业设计基于深度强化学习的双目标动态感知路径规划python源码.zip毕业设计基于深度强化学习的双目标动态感知路径规划python源码.zip毕业设计基于...
前端开发学习宝典:从入门到精通的路径规划 前端开发是现代Web开发的重要组成部分,掌握前端技术对于成为一名优秀的Web开发者至关重要。本文将详细介绍前端开发的学习路线,并提供具体的学习建议和示例。 基础编程...
第09章项目实战2-电商网站,实现动态网网站的数据抓取 第10章实战项目3-社区网站,实现模拟登陆和验证码 第11章先懂反爬再应对反爬 第12章学会用框架,scrapy实现快速开发爬虫 第13章帮你规划一条通往高级爬虫工程师...
ACM课件(5)_动态规划(2) ACM课件(6)_计算几何基础 ACM课件(7)_贪心算法 ACM课件(8)_搜索入门 ACM课件(9)_二分匹配入门 ACM课件(10)_母函数及其应用 ACM课件(11)_特殊的数 ACM课件(12)_博弈入门 ACM课件(13)_...
全书内容分为12 章,包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、C++与STL入门、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法、高级专题等内容,...
### 3-动态规划(Dynamic Program) 1. [网格游戏在均匀策略下的策略评估例子] 2. [策略迭代算法流程图] 3. [网格游戏在贪婪策略下的策略迭代例子] 4. [值迭代算法流程图] 5. [网格游戏在贪婪测略下的值迭代例子] 6. ...
运筹学入门课件: 1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析 8.图与网络分析
ACM课件(5)_动态规划(2) ACM课件(6)_计算几何基础 ACM课件(7)_贪心算法 ACM课件(8)_搜索入门 ACM课件(9)_二分匹配入门 ACM课件(10)_母函数及其应用 ACM课件(11)_特殊的数 ACM课件(12)_博弈入门 ACM课件(13)_并查集
│ 6:15分钟搞懂动态规划 │ 7:15分钟搞懂二分搜索与贪婪 │ 8:大厂高频真题精讲(一) │ 9:大厂高频真题精讲(二) │ 10:大厂算法面试难题精讲(一)上 │ 10:大厂算法面试难题精讲(一)下 │ 11:大厂算法面试...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_...(lecture_13)动态规划(2) 并查集