动态规划 导弹拦截

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

 第一问思路非常简单,不断改变终止点的位置,更新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 条评论
登录 后参与评论

相关文章

来自专栏风中追风

分布式进阶__zookeeper的zab协议工作原理之 崩溃恢复模式

上篇 zookeeper的zab协议工作原理之 原子广播 介绍了 zookeeper 广播的原理。

34310
来自专栏乐沙弥的世界

Percona XtraDB Cluster多主复制(PXC 5.7 )

Percona XtraDB Cluster(下称PXC)集群是一种支持多主方式的集群模式,也就是说多个不同的节点均可提供读写功能,并且确保写入对群集中的所有节...

782
来自专栏liulun

windows服务器性能监控工具、方法及关键指标

监控方法 推荐使用windows自带的“性能监视器”(老版本的windows叫性能计数器)来监控服务器的性能。 打开控制面板内的管理工具,在管理工具内打开性能监...

2726
来自专栏Albert陈凯

Spark中Task,Partition,RDD、节点数、Executor数、core数目的关系

Spark中关于并发度涉及的几个概念File,Block,Split,Task,Partition,RDD以及节点数、Executor数、core数目的关系。 ...

3346
来自专栏Hadoop实操

Slow ReadProcessor&amp;Error Slow BlockReceiver错误日志分析

4334
来自专栏Hadoop实操

如何使用Cloudera Manager在线为集群减容

在Hadoop集群资源紧张的情况下可以在线扩容来提升集群的计算能力,具体参考Fayson前面的文章《如何在非Kerberos环境下对CDH进行扩容》,那么在集群...

8187
来自专栏数据和云

YH4:Oracle Flex Clusters

从Oracle数据库12c开始,可以将Oracle Clusterware和Oracle RAC配置在大型集群中,称为Oracle Flex集群。 这些集群包含...

2605
来自专栏数据和云

从 Elasticsearch 来看分布式系统架构设计

云栖君导读: 分布式系统类型多,涉及面非常广,不同类型的系统有不同的特点,批量计算和实时计算就差别非常大。这篇文章中,重点会讨论下分布式数据系统的设计,比如分布...

5076
来自专栏linux驱动个人学习

TLB和MMU的区别

MMU是Memory Management Unit的缩写,中文名是内存管理单元,它是中央处理器(CPU)中用来管理虚拟存储器、物理存储器的控制线路,同时也负责...

3425
来自专栏Java进阶

zookeeper的zab协议工作原理之 崩溃恢复模式

3047

扫码关注云+社区