拦截导弹问题 简单DP(LIS)

题目大意:
为了拦截敌国的袭击,科学家研发出一套导弹系统,导弹系统有个缺陷:第一发炮弹可以到达任意高度,然而之后的每一发炮弹都不能高于前一发的高度。
现给出数个导弹的高度( <=50000的正整数 ):
389,207,155,300,299,170,158,65,
计算一套导弹拦截系统最多可以拦截多少导弹,如果需要拦截全部导弹需要多少套导弹拦截系统?

这题是一道LIS模板题,第一问很好想到就是求最长的非递增序列,但是第二问不好想。
LIS(Longest Increasing Subsequence)动态规划思路:
先不考虑题目,单求最长上升子序列(不含相等)。
简单案例:1,3,2,6,4,5
(下面的长度即是最优解的意思)
1处的长度显然为1;
3处显然是1的长度+1;
2处是1处长度+1;
6处是3处(或2处)长度+1;
4处是3处(或2处)+1;
5处是4处+1(而不是2、或3);
显然,后面的元素对应最优解是前面小于该元素中最优解最大的+1;
有如此的状态转移方程:
dp[i] = max(dp[j]+1);/代码中要变通 / ( 0 <= j < i );

个人对第二问的理解:
个人不是很懂原理,只能借助图像来辅助理解(太菜了):
拦截导弹问题  简单DP(LIS)
(图画的不好hh。。)
①号线的长度:2,是原题目的情况下,需要的导弹次数;
可以这么理解,如果长度为1,代表左边的207和155不存在,现在既然存在了,代表需要多一个导弹系统,另外处理这两个导弹了,(长度刚刚好就是2。。)。

②号线的长度为:3,显然,不能跟第一次一起拦截,也不能和前面的 207和 155一起处理,刚好长度是3(因为有160的存在才多了一个)。

代码(走案例):

#include<iostream>
using namespace std;
#define __max(a,b) (((a) > (b)) ? (a) : (b))
#define N 8
int H[9] = {389,207,155,300,299,170,158,65};
int up[9];//最长上升序列,不含=
int down[9];//最长下降序列,含=
int main()
{
    int len_up = 0/*第二问*/, len_down = 0/*第一问*/;
    for (int i = 1; i <= N ; i++)
    {
        up[i] = 0;
        down[i] = 0;
        for(int j = 0 ; j < i ; j++)
        {
            if(H[j]/*H[j]不比H[i]小*/ >= H[i])
            {
                down[i] = __max(down[j]+1,down[i]);
            }
            if(H[j]/*H[j]比H[i]小*/ < H[i])
            {
                up[i] = __max(up[j]+1,up[i]);/*取j中up[j]最大的*/
            }
        }
        // printf("高度%d ,up : %d\n",H[i],up[i]);
        len_up = __max(up[i],len_up);
        len_down = __max(down[i],len_down);
    }
    printf("%d\n%d",len_down,len_up);
    return 0;   
}

(蓝桥杯备赛笔记)

上一篇:HTML链接标签


下一篇:BigDecimal加减乘除计算