题目描述

题目链接：https://ac.nowcoder.com/acm/problem/16810
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入

389 207 155 300 299 170 158 65

输出

6
2

解题思路

很容易理解这道题目要求我们求数列的最长非增序列长度和最长增序列长度（证明可参考Dilworth定理），前面的证明已经有大佬写的非常清楚了，这份题解我这个菜鸡主要说一下他们的求法，我们需要用两个数组，一个储存当前元素的值，另一个记录在此元素之前（可以包括此元素，无非是最后加不加1）能加入此元素的序列长度我们举个例子，我们来求最长非增序列
389 207 155 300 299 170 158 65

我们第一次是389，可以单独形成一个符合条件的序列，因此我们第二个数组就更新成了
1 0 0 0 0 0 0 0

第二次到了207，207的前方有389如果把207加入其中也是符合非增序列的，在这里我们有两个选择，第一个加入389的序列（长度为2），第二个自己单独形成一个序列（长度为1）因此第二次我们选择了第一个方案，因此我们的数组更新为
1 2 0 0 ......

第三次155，加入哪个序列都可以，我们选择最长的，因此数据更新为
1 2 3 0 ......

第四次300，只符合加入389的序列或者自己单独成一个序列，选择最长的，
1 2 3 2 0......

第五次299
1 2 3 2 3 0......
第六次170
1 2 3 2 3 4 0 ......
第七次158
1 2 3 2 3 4 5 0
第八次65
1 2 3 2 3 4 5 6
389 207 155 300 299 170 158 65
我们选择统计数组里面最大的6就是最长的非增序列

通过代码

（代码不够简练，而且我是倒着从65开始的，有时间我会改下代码）

#include<stdio.h>
int s[100000],count[100000],countt[100000];
int main(){
    int i=0;
    while (~scanf("%d",&s[i]))
    {
        i++;
    }
    i--;
    for (int j = i; j >= 0; j--)
    {
        for (int k = j; k <= i; k++)
        {
            if (s[j]>=s[k]&&count[k]+1>count[j])
            {
                count[j]=count[k]+1;
            }
        }
    }
    for (int j = i; j >= 0; j--)
    {
        for (int k = j; k <= i; k++)
        {
            if (s[j]<s[k]&&countt[k]+1>countt[j])
            {
                countt[j]=countt[k]+1;
            }
        }
    }
    int max=-1,maxx=-1;
    for (int h = 0; h <= i; h++)
    {
        if (count[h]>max)
        {
            max=count[h];
        }
        if (countt[h]>maxx)
        {
            maxx=countt[h];
        }
    }
    printf("%d\n%d",max,maxx+1);
    return 0;
}

PS：菜鸡第一次写题解，希望大佬多指点。