ACM题目————又见拦截导弹

描述

大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度。突然有一天,雷达捕捉到敌国的导弹来袭。由于该系统存在缺陷,所以如果想把所有的导弹都拦截下来,就要多准备几套这样的导弹拦截系统。但是由于该系统成本太高,所以为了降低成本,请你计算一下最少需要多少套拦截系统。

输入
有多组测试数据。
每组数据先输入一个整数N(N≤3000),代表有N发导弹来袭。接下来有N个数,分别代表依次飞来的导弹的导弹的高度。当N=-1时表示输入结束。
输出
每组输出数据占一行,表示最少需要多少套拦截系统。
样例输入
8
389 207 155 300 299 170 158 65
5
265 156 123 76 26
样例输出
2
1

没有想到竟然是结束条件的错误T_T。。

题目简单,就是动态规划。唉,不能粗心啊!

//Asimple
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <string>
#include <queue>
#define INF 0xffffff
using namespace std;
const int maxn = 3000+5;
typedef long long ll ;
int n, ans;
int a[maxn], m[maxn];

int main(){
    while(~scanf("%d",&n) && n != -1){
        for(int i=0; i<n; i++){
            scanf("%d",&a[i]);
            m[i] = 1;
        }
        ans = 1;
        for(int i=0; i<n; i++){
            for(int j=i-1; j>=0; j--){
                if( a[j] < a[i] && m[i]<m[j]+1)
                    m[i] = m[j]+1;
            }
            if( ans < m[i] ) ans = m[i] ;
        }
        printf("%d\n",ans);
    }
    return 0;
}       
时间: 07-21

ACM题目————又见拦截导弹的相关文章

nyoj 814 又见拦截导弹

又见拦截导弹 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.突然有一天,雷达捕捉到敌国的导弹来袭.由于该系统存在缺陷,所以如果想把所有的导弹都拦截下来,就要多准备几套这样的导弹拦截系统.但是由于该系统成本太高,所以为了降低成本,请你计算一下最少需要

又见拦截导弹

又见拦截导弹 描述 大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.突然有一天,雷达捕捉到敌国的导弹来袭.由于该系统存在缺陷,所以如果想把所有的导弹都拦截下来,就要多准备几套这样的导弹拦截系统.但是由于该系统成本太高,所以为了降低成本,请你计算一下最少需要多少套拦截系统. 输入 有多组测试数据. 每组数据先输入一个整数N(N≤

NYOJ814又见拦截导弹(平台最优程序)

又见拦截导弹 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.突然有一天,雷达捕捉到敌国的导弹来袭.由于该系统存在缺陷,所以如果想把所有的导弹都拦截下来,就要多准备几套这样的导弹拦截系统.但是由于该系统成本太高,所以为了降低成本,请你计算一下最少需要

codevs 1044 拦截导弹 1999年NOIP全国联赛提高组

1044 拦截导弹 1999年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 题目描述 Description 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 输入描述 Input Description 输入导弹

1044 拦截导弹

1044 拦截导弹 1999年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. 输入描述 Input Description 输入导弹依次飞

拦截导弹

[题目描述] Description 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹. [输入描述] Input Description 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数) [输出描述] Output Description 输出这套系统最多能

拦截导弹;合唱队形;友好城市——基本的单调序列动态规划吧

合集,三个题目基本上都一样.耗时也不贴了. 拦截导弹: 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int N=128; 5 int n=1,val[N]; 6 int up[N],dn[N],cnt1,cnt2; 7 int main(){ 8 for(int i=0;i<N;i++)up[i]=dn[i]=1; 9 while(cin>>val[n])n++;n-

codevs1409 拦截导弹2

[问题描述]一场战争正在 A 国与 B 国之间如火如荼的展开.B 国凭借其强大的经济实力开发出了无数的远程攻击导弹,B 国的领导人希望,通过这些导弹直接毁灭 A 国的指挥部,从而取得战斗的胜利!当然,A 国人民不会允许这样的事情发生,所以这个世界上还存在拦截导弹.现在,你是一名 A 国负责导弹拦截的高级助理.B 国的导弹有效的形成了三维立体打击,我们可以将这些导弹的位置抽象三维中间的点(大小忽略),为了简单起见,我们只考虑一个瞬时的状态,即他们静止的状态.拦截导弹设计非常精良,可以精准的引爆对方

拦截导弹(南阳oj)(dp最长下降子序列)

拦截导弹 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发的高度.某天,雷达捕捉到敌国导弹来袭.由于该系统还在试用阶段,所以只用一套系统,因此有可能不能拦截所有的导弹. 输入 第一行输入测试数据组数N(1<=N<=10) 接下来一行输入这组测试数据共有多少个导弹m(1<=m<=20) 接下来行输

百练2945 拦截导弹

描述 某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹.拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹. 输入 输入有两行,第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出