动态规划之导弹拦截问题
动态规划之导弹拦截问题
今天你学习了吗
康康题目吧
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）
1.计算一套系统最多能拦截多少导弹？
2.如果要拦截所有导弹，最少要配备多少套这种导弹拦截系统？
问题分析
第一问很好理解就是求最长非上升子序列，动态规划经典题目，极端情况是如果发来的导弹高度依次递减或不变，那么一个拦截系统就可以全部拦截，如果发来的导弹高度依次递增，那么一台系统最多拦截一个导弹。
第二问
方法一：应用贪心算法，每次取最长不上升子序列，然后在剩下的数中循环求最长不上升子序列，直到取完为止。
方法二：转化成求最长上升子序列的长度，这涉及组合数学中的Dilworth定理.
狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目
Dilworth定理：不上升子序列的最小划分数=最长上升子序列的长度.
本文主要运用方法二动态规划思想。
代码部分
C++求最长不上升子序列和最长上升子序列
#include <iostream>
#include <algorithm> //min,max函数
#include <memory.h>
#define N 30
using namespace std;
int a[N]; //定义输入数组
int down[N]; //最长不上升子序列数组
int up[N]; //最长上升子序列数组
int ans=0;
int n=0;
int x=0; //初始化
int y=0; //初始化
char c;
int main()
{
while(1){
cin>>a[n]; //n是输入导弹的个数
n++;
c=cin.get();
if(c=='\n')
break;
}
for(int i=0;i<n;i++)
{
down[i]=1;
up[i]=1; //保证最少可以拦截一个导弹
for(int k=0;k<i;k++)
{
if(a[i]<=a[k]){
down[i]=max(down[i],down[k]+1); //最长下降子序列当前的长度
}
else{
up[i]=max(up[i],up[k]+1); //最长上升子序列当前的长度
}
}
x=max(x,down[i]); //随着当前数组遍历长度（i）的增加,x依次被更新，x始终是当前的最长下降子序列长度
y=max(y,up[i]); //随着当前数组遍历长度（i）的增加,y依次被更新，y始终是当前的最长上升子序列长度
}
cout<<x<<endl;
cout<<y;
return 0;
}
具体实例分析
a[0] a[1] a[2] a[3] a[4]
例如：389 207 155 300 299
***i=0 , down[0]=up[0]=1***
k=0, 第二个for循环进不去
x=max(0,down[0])=1 , y=max(0,up[0])=1
***i=1 ,down[1]=up[1]=1***
k=0,a[1]<a[0],down[1]=max(down[1],down[0]+1)=2
x=max(1,down[1])=2 , y=max(1,up[1])=1
***i=2,down[2]=up[2]=1***
k=0,a[2]<a[0],down[2]=max(down[2],down[0]+1)=2
k=1,a[2]<a[1],down[2]=max(down[2],down[1]+1)=3
x=3,y=1
***i=3,down[3]=up[3]=1***
k=0,a[3]<a[0],down[3]=max(down[3],down[0]+1)=2
k=1,a[3]>a[1],up[3]=max(up[3],up[1]+1)=2
k=2,a[3]>a[2],up[3]=max(up[3],up[2]+1)=2
x=max(x,down[3])=3,y=2
***i=4,down[4]=up[4]=1***
k=0,a[4]<a[0] down[4]=max(down[4],down[0]+1)=2
k=1,a[4]>a[1]
up[4]=max(up[4],up[1]+1)=2
k=2,a[4]>a[2]
up[4]=max(up[4],up[2]+1)=2
k=3,a[4]<a[3]
down[4]=max(down[4],down[3]+1)=3
x=3,y=2
附python代码
while True:
try:
s = list(map(int,input().split())) #输入导弹飞行高度,空格输入,回车结束输入,存为列表
n = len(s) #计算长度
dp = [1 for i in range(n)] #最多拦截导弹数
dp2 = [1 for i in range(n)] #要拦截所有导弹最低配置
for i in range(n):
for j in range(i):
if s[i] < s[j]: #s[i] 是当前的数字,j是动态的
dp[i] = max(dp[i],dp[j]+1)
else:
dp2[i] = max(dp2[i],dp2[j]+1)
print(max(dp))
print(max(dp2))
except:
break