6.导弹对对碰

6.导弹对对碰

时间： 1ms        内存：128M

描述：

小明现在玩一个很有意思的手机游戏，游戏内容是敌方堡垒发射导弹，每个导弹都有不同的高度，小明作为守护方，发射以和敌方导弹高度相同的炮弹来阻截敌方发来的导弹，但毕竟小明不是人民币玩家，游戏规则是他发的炮弹高度只能越来越低，连和上次发射高度相同高度的炮弹都无法第二次发射出来，初始化小明有5滴血，敌方每一枚导弹打到守护方，守护方都会掉一滴血，0血游戏失败。

输入：

输入有两行

第一行，输入敌方导弹的数量n（n<=25）

第二行输入n个正整数，表示n枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔

输出：

若守护方可以生存，输出最多可以拦截多少枚导弹，若不能生存，输出 No

示例输入：

6
100 100 9 8 7 6

示例输出：

5

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
#include<stdlib.h>

const int maxn = 25;
int mmax[maxn];
int height[maxn];
const int HP = 5;
int max_intercept_missile = 1;
int n;
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",height+i);
        mmax[i] = 1;
    }
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
            if(height[i]<height[j])
                mmax[i] = mmax[i] < mmax[j] + 1 ? mmax[j] + 1 : mmax[i];
        max_intercept_missile = max_intercept_missile < mmax[i] ? mmax[i] : max_intercept_missile;
    }
    printf(n-max_intercept_missile>=HP?"No\n":"%d\n",max_intercept_missile);
    return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<stdlib.h>

const int maxn = 25;
int mmax[maxn];
int height[maxn];
const int HP = 5;
int max_intercept_missile = 1;
int n;
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",height+i);
        mmax[i] = 1;
    }
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
            if(height[i]<height[j])
                mmax[i] = mmax[i] < mmax[j] + 1 ? mmax[j] + 1 : mmax[i];
        max_intercept_missile = max_intercept_missile < mmax[i] ? mmax[i] : max_intercept_missile;
    }
    printf(n-max_intercept_missile>=HP?"No\n":"%d\n",max_intercept_missile);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。