【动态规划】拦截导弹_dilworth定理_最长递增子序列

问题 K: 【动态规划】拦截导弹

时间限制: 1 Sec 内存限制: 256 MB
提交: 39 解决: 10
[提交][状态][讨论版] </center>

题目描述

张琪曼：“老师，修罗场是什么？”

墨老师：“修罗是佛家用语，修罗毕生以战斗为目标，修罗场指的是他们之间的死斗坑，人们通常用‘修罗场’来形容惨烈的战场。后来又引申出‘一个人在困境中做绝死奋斗’的意思。所以，这其实也在暗示我们，即使是身处绝境，也不要放弃奋斗。再说了，情况其实没有这么糟糕，因为我们最新的导弹拦截系统已经研制好了。”

魔法世界为了防御修罗王军团的导弹袭击，开发出一种导弹拦截系统──“要你命3000”。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到修罗王军团的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

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

输入

一行，为导弹依次飞来的高度

输出

行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6
2

解题思路：题目所给的数据并不知道数量，所以添加一个字符，genchar（）获取字符判断是不是空格，是空格说明后面还有数据，继续读入整数。

    char cc;
    cin>>a[n++];
    while((cc=getchar())==' '){
        cin>>a[n++];
    }

　　本来我是用的cc=getchar（）！=‘\n’,结果提交oj，显示超时，程序根本停不下。所以不知道一行的最后用什么结束的，但改成只要不等于空格就结束，就可以了。　

　　最多能拦截的导弹数很容易明白，就是求最长非递增子序列。

　　最少要配备的系统数，刚开始我以为只要后面一个数比前面一个数大，然后c++，最后得到的就是要配备的系统数呢。

　　但7 8 9 2 1 3 4 5这几个数就不可以，得到的是5，但结果应该是4。 5虽然比4大，但是他可以被打掉9的导弹打掉。所以5就不用再计入了。

　　后来百度一下，应该是求最长递增子序列才行。

　　然后证明这个好像是什么dilworth定理（最少链划分 = 最长反链长度）。

　　这个还不太懂，一会再看看。

　　还有个理解的方法，这个序列可以挑出很多递增子序列来，找一个不是最长的，再看他后面可能还有一个比这个序列中大的一个数，这个数也要消耗一个导弹。所以得找最长递增子序列才能打掉所有导弹。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n=0;
    int a[10000];
    int sum[10000];
    int sum2[10000];
    int c=0;//储存下一个高度比上一个高度大的情况数量
    int maxx;
    int maxx2;
    int ans=1;
    int ans2=1;
    char cc;
    cin>>a[n++];
    while((cc=getchar())==' '){
        cin>>a[n++];
    }
    sum[0]=1;
    sum2[0]=1;
    for(int i=1;i<n;i++){
        maxx=0;
        maxx2=0;
        for(int j=0;j<i;j++){
            if(a[j]>=a[i]){
                maxx=max(maxx,sum[j]);
            }
            if(a[j]<a[i]){
                maxx2=max(maxx2,sum2[j]);
            }
        }
        sum[i]=maxx+1;
        ans=max(ans,sum[i]);
        sum2[i]=maxx2+1;
        ans2=max(ans2,sum2[i]);
    }
    printf("%d\n%d",ans,ans2);
    return 0;
}