【3005】拦截导弹问题（noip1999）

Time Limit: 3 second

Memory Limit: 2 MB

某国为了防御帝国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然他的第一发炮弹能达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以这套系统有可能不能拦截所有的导弹。

输入导弹一次飞来的高度（雷达给出的高度是不大于2147483647的正整数）。计算要拦截所有导弹时最小需要配备所少套这种导弹拦截系统。

Input

输入文件两行

第一行输入n

第二行输入n颗依次飞来的导弹高度，输入的各个元素用空格隔开(1≤n≤1000)。

Output

输出要拦截所有导弹最小配备的系统数k。（最后用换行结束）

Sample Input

8

389 207 155 300 299 170 158 65

Sample Output

【题解】

打导弹的过程就是求最长下降子序列的过程，每次都求最长的，让每个导弹的效果达到最大。

打完后的导弹，用一个bool型数组置为false，下一次扫描的时候，直接跳过就可以了.

【代码】

#include <cstdio>

int n,a[1002],f[1002],ans = 0,rest,pre[1002],now,maxn = 0;

bool bo[1002];

void input_data()

{

    scanf("%d",&n);

    for (int i = 1;i <= n;i++)

        scanf("%d",&a[i]);

    rest = n;

    for (int i = 1;i <= n;i++) //一开始所有的导弹都可以打得到。

        bo[i] = true;

}

void get_ans()

{

    while (rest > 0)

        {

            for (int i = 1;i <= n;i++) //for 每一个导弹

                if (bo[i]) //如果这个导弹之前未被打过

                {

                    f[i] = 1; //表示以第i个导弹为最长下降序列的最后一个数 的序列的长度。

                    pre[i] = -1; //这个pre数组用于最后标记那些已经被打过的导弹序号.

                    if (f[i] > maxn) //如果能更新最大长度 就更新，同时记录这个尾数字。方便找序列

                        {

                            maxn = f[i]; //更新最大值

                            now = i;    //记录位置

                        }

                    for  (int j = 1;j <= i-1;j++) //往前面尝试更新f[i]

                        if (bo[j] && a[i] <= a[j] && ((f[j] + 1) > f[i])) //没有用过 满足递减 有更新必要

                            {

                                f[i] = f[j] +1; //更新f[i]

                                pre[i] = j; //记录上一个数的位置

                                if (f[i] > maxn)

                                    {

                                        maxn = f[i];

                                        now = i;

                                    }

                            }

                }

            while (now != -1) //如果没有输出到根 就继续输出

                {

                    bo[now] = false;

                    rest--;

                    now = pre[now];

                }

            ans++;

            maxn = 0;

        }

}

void output_ans()

{

    printf("%d\n",ans);

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    input_data();

    get_ans();

    output_ans();

    return 0;

}

巴特西

【3005】拦截导弹问题（noip1999）

Input

Output

Sample Input

Sample Output

最新文章

热门文章