动态规划 导弹拦截

题意:一种导弹拦截系统的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度,计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统?

 第一问思路非常简单,不断改变终止点的位置,更新dp数组。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[1010],a[1010];
int main()
{
    int cases;
    cin>>cases;
    while(cases--)
    {
        memset(dp,0,sizeof(dp));
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        dp[0]=1;//最小子序列一定是1,没有更小的了
        for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
        if(a[i]<a[j]&&dp[j]+1>dp[i]){dp[i]=dp[j]+1;}
        cout<<*max_element(dp,dp+n)<<endl;
    }
}

第二问难度比较大

我们把第二问的问题抽象出来,那就是:把一个数列划分成最少的最长不升子序列。

Dilworth定理

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[1010],a[1010];
int main()
{
    int cases;
    cin>>cases;
    while(cases--)
    {
        int n;
        cin>>n;
        fill(dp,dp+n,1);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        dp[0]=1;//最小子序列一定是1,没有更小的了
        for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
        if(a[j]<a[i]&&dp[j]+1>dp[i]){dp[i]=dp[j]+1;}//changes;
        cout<<*max_element(dp,dp+n)<<endl;
    }
}

思路就是从头录到tail,能摁在一块的安一快。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Crossin的编程教室

【每周一坑】美队盾牌

大家好,最近更新频率又慢了,【每周一坑】快变成【每两周一坑】了……不过别急,我们正在酝酿一些好玩又实用的内容和活动,很快会陆续奉上。 刚刚加入不久朋友,如果是初...

2936
来自专栏Python中文社区

GayHub用户及仓库分析爬虫

專 欄 ❈陈键冬,Python中文社区专栏作者 GitHub: https://github.com/chenjiandongx ❈ 爬虫介绍 Github ...

2397
来自专栏chenssy

美团面试经历,贡献出来一起学习

美团我是在拉勾网上投的简历,之前也投过一次,简历都没通过删选,后来让学姐帮我改了一下简历,重新投另一个部门,获得了面试机会。10月23日中午HR打电话过来预约了...

1032
来自专栏程序员互动联盟

如何提高编写代码的速度?

如何提高代码编写的速度,一直是一个逃避不了的问题。在天朝你得像打字员一样做程序员,不然老板和上司都觉得你是在玩耍。对项目的贡献体现在哪里?码农难道不是以code...

3878
来自专栏java一日一条

不愿看到Java开发者再做的10件事

编者注:Andy是OSI(开发系统集成者)的CEO,同时也是位思想先锋及优秀博客作者。

432
来自专栏落影的专栏

新鲜出炉的iOS面试题

为防止背题,大部分题目不设标准答案,重点考察面试者的基础知识和思维逻辑,答案的提示见后面。

1472
来自专栏一名叫大蕉的程序员

餐厅老板要累疯了No.2

我是小蕉。 从前有座山,山里有座庙,庙里有个老和尚,阿不,有个餐厅的老板,在每天午餐之前,都要自己亲力亲为为各个小伙伴分配任务,大喊一声开饭啦,大家就屁...

1759
来自专栏北京马哥教育

据说这篇总结覆盖了一般Python开发面试中可能会问到的大部分问题

通信背景,工作一年多不到两年。之前一直在做C++的MFC软件界面开发工作。公司为某不景气的国企研究所。(喏,我的工作经验很水:1是方向不对;2是行业有偏差)。然...

1092
来自专栏前端儿

拦截导弹

某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发...

842
来自专栏恰同学骚年

自己动手写游戏:飞机大战

  要说微信中最火爆的小游戏是哪款,可能既不是精心打造的3D大作,也不是《植物大战僵尸2》,而是微信5.0刚开启时的《飞机大战》。

1661

扫码关注云+社区