NOIP 1999 导弹拦截

洛谷 P1020 导弹拦截

https://www.luogu.org/problemnew/show/P1020

JDOJ 1411: [NOIP1999]拦截导弹 T1

https://neooj.com:8082/oldoj/problem.php?id=1411

题目描述

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

输入导弹依次飞来的高度（雷达给出的高度数据是\le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式：

11行，若干个整数（个数\le 100000≤100000）

输出格式：

22行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入样例#1： 

389 207 155 300 299 170 158 65

输出样例#1： 

6

2

动态规划的一道题。
第一问求最长不上升子序列。
问题是第二问。
第二问的正解是求最长上升子序列。
看了好长时间才看懂大佬们的证明过程。
原文：

（1）假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹。

（2）假设我们得到了最小划分的K组导弹，从第a(1<=a<=K)组导弹中任取一个导弹，必定可以从a+1组中找到一个导弹的高度比这个导弹高（因为假如找不到，那么它就是比a+1组中任意一个导更高，在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组），同样从a+1组到a+2组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来，连成一条上升子序列，其长度即为K;

（3）设最长上升子序列长度为P，则有K<=P;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升)，则有

P>=K，所以K=P。

大意：
随便找一个导弹开打，重复。
最不理想状态下，得到了最小划分的导弹组数（就是最差情况）。
在某一组中找任意一颗导弹，肯定会在这组的下一组中找到一个比它还高的。
很好证，因为假如找不到比这还高的，就说明这颗导弹比所有的都要高，应该被下一组直接打下来，而不应该存在于这个位置。
那么我们就可以在每一组找一个这样的导弹，依次连接，肯定是一条上升子序列。
证毕。

PS：这里还要注意读入的问题，坑爹的JDOJ上的输入输出样例跟原题（洛谷上的）完全不一样，需要用字符串。

这里免去这么多没有用的冗长代码，直接上洛谷AC100分的（用什么树状数组，线段树能写200分的，但是我不会）

Code:

#include<cstdio>

#include<algorithm>

using namespace std;

int n,a[],f[],p[];

int ans1,ans2;

int main()

{

    while(scanf("%d",&a[++n])!=EOF);

    n--;

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

    {

        f[i]=;

        for(int j=;j<=i-;j++)

            if(a[i]<=a[j])

                f[i]=max(f[i],f[j]+);

        ans1=max(ans1,f[i]);

    }

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

    {

        p[i]=;

        for(int j=;j<=i-;j++)

            if(a[i]>a[j])

                p[i]=max(p[i],p[j]+);

        ans2=max(ans2,p[i]);

    }

    printf("%d\n%d",ans1,ans2);

    return ;

}