HDOJ1257最少拦截系统

题目链接:HDOJ1257

 这个题一开始我百思不得其解,后来看了一眼别人的题解标题,最长上升子序列?我当时还纳闷,这和最长上升子序列有什么关系,后来仔细一想还确实是。因为导弹拦截系统每次打击的高度只能越来越低,那么我就找越来越高的导弹高度又多少个就行了  举个例子,假设导弹高度分别是2 3 1 4 7,输出应该是4,需要4套拦截系统,五发导弹,为什么只要4个?因为在2 3 4 7这个最长上升子序列中间混入了一个1,1肯定是要比前面的3要小,所以能打击到3的,一定能打击到1,因此1就不用管了,但是越来越高的高度是没法拦截的,所以需要针对2 3 4 5四个导弹分别设一个拦截系统

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int arr[] = new int[10000];
            int dp[] = new int[10000];
            int t = cin.nextInt();
            int ans = 1;
            for(int i = 0;i < t;i++) {
                arr[i] = cin.nextInt();
                dp[i] = 1;
                for(int j = 0;j < i;j++) {
                    if(arr[i] > arr[j])//i作为结尾比j大,构成最长上升子序列
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                }
                ans = Math.max(dp[i],ans);
            }
            System.out.println(ans);
        }
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

十步零基础JavaScript学习路径

之前写过一篇26天学通前端开发,内容主要讲的就是前端学习路径,今天再来写一篇零基础的JavaScript学习路径,希望能帮编程零基础的前端爱好者指明方向。 开发...

21290
来自专栏怀英的自我修炼

Java漫谈2

本周我们的Java漫谈从一个段子说起。话说有一个老程序退休了,在家闲着没事便开始学习写毛笔字,焚香,研墨,铺纸。站在薄如蝉翼白似雪的宣纸面前,提笔闭目。只见那人...

34380
来自专栏编程微刊

JavaScript基础

18620
来自专栏陈纪庚

使用装饰者模式做有趣的事情

装饰者模式是一种为函数或类增添特性的技术,它可以让我们在不修改原来对象的基础上,为其增添新的能力和行为。它本质上也是一个函数(在javascipt中,类也只是函...

8620
来自专栏PHP在线

编程语言中的闭包

首先,我觉得,一个概念,如果不理解也不影响使用的话,那么,就没必要去理解它、去学习它。闭包就是这样一个概念,你不理解它也能很好的用它。俺这两年写as3程序,是天...

38740
来自专栏java工会

深度思考编程的艺术

18280
来自专栏Android 开发者

[译] Kotlin 揭秘:理解并速记 Lambda 语法

在奥地利旅行期间,我参观了维也纳的奥地利国家图书馆。特别是国会大厅,这个令人惊叹的空间感觉就像印第安纳琼斯电影中的一些东西。房间周围的空间是这些门被装在架子上,...

9700
来自专栏编程

Java 最困扰你的那些事

啊哈Reddit(某知名国外在线问答社区),没了你我们还能在哪里从鱼目混珠的网络中提炼真正的精华?就在这杂乱无章的论坛中,的的确确存在着这样一些精辟的讨论。 比...

22680
来自专栏java一日一条

哪些因素影响Java调用的性能?

这得从一个小故事说起。我在一个Java核心库的邮件列表中提交了一个修改 ——重写了一些本是 final 的方法。一石激起千层浪,这一改动引发了几番讨论。而其中一...

13710
来自专栏程序员的诗和远方

20180803_ARTS_week06

这个是个比较不好的解法,就是像题目介绍里面那样先把这个『之』字形给做出来,然后再逐行读成字符串,但是通过这个比较好帮助我们理解这个题目。

10010

扫码关注云+社区

领取腾讯云代金券