动态规划之拦截导弹(openjudge)

时间限制: 1 Sec
内存限制: 64 MB

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入

第1行：依次输入若干个导弹的高度H(1≤H≤30000)，导弹的个数N≤5000

输出

第1行：一个整数，表示单枚炮弹能拦截多少导弹 第2行：一个整数，表示拦截所有导弹最少要配备多少套这种导弹拦截系统

样例输入

389 207 155 300 299 170 158 65

样例输出

6
2

提示

第2问最直观的算法是贪心，但是反例也容易找到，如：
6 5 1 7 3 2
如果第一次打6 5 3 2,显然还要打两次，而最好的方案是6 5 1/7 3 2。

题目分析

显然，此题的第一问就是一个简单的最长下降子序列，它和我们的最长上升子序列相差无几（只是符号不同罢了）。它既可以用‘我为人人’也可以用‘人人为我’的方法。而下面这个方法大概是改良后的吧。而第二题，我们也可以用两种方法来做：第一种使我们前面所学的贪心算法，第二种则是求出最长上升子序列。为什么可以用最长上升子序列呢？其实这是和贪心一样的思路。
就像上图一样，一旦遇到上升的导弹就一定会用第二套导弹系统。没有其他方法能将上升序列的两个导弹一起打下来。所以此题也就可以转化到最长下降子序列和最长上升子序列。既是如此，那此题就简单了。

代码解析

状态：AC

#include<bits/stdc++.h>
using namespace std;
int a[5005][4];
int b[5005][4];//a[][1]值，a[][2]长度,a[][3]前驱
int n;
int main()
{
 int l,k;
 int n=1;
 while(scanf("%d",&a[n][1])!=EOF)
 {
    
 a[n][2]=1;a[n][3]=0;
 b[n][1]=a[n][1];b[n][2]=1;b[n][3]=0;
 n++;
 } for(int i=n-1;i>=1;i--)
 {
    
 l=0;k=0;
 for(int j=i+1;j<=n;j++)
 if((a[j][1]<a[i][1])&&a[j][2]>l)
 {
    
 l=a[j][2];
 k=j; 
 } 
 if(l>0)
 {
    
 a[i][2]=l+1;
 a[i][3]=k; 
 }
 }
 k=1;
 for(int j=1;j<=n;j++)
 if(a[j][2]>a[k][2])k=j;
 printf("%d\n",a[k][2]); l=0;k=0;
 for(int i=n-1;i>=1;i--)
 {
    
 l=0;k=0;
 for(int j=i+1;j<=n;j++)
 if((b[j][1]>b[i][1])&&b[j][2]>l)
 {
    
 l=b[j][2];
 k=j; 
 } 
 if(l>0)
 {
    
 b[i][2]=l+1;
 b[i][3]=k; 
 }
 }
 k=1;
 for(int j=1;j<=n;j++)
 if(b[j][2]>b[k][2])k=j;
 int num=0;
 int s=k;
 printf("%d\n",b[k][2]);}