NOIP 1999 导弹拦截(DP)

迷南。 2022-05-17 09:07 334阅读 0赞

题目描述：

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

输入：

每个测试文件只包含一组测试数据，每组输入若干个整数，表示导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）

输出：

对于每组输入数据，第一行输出这套系统最多能拦截多少导弹，第二行输出如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

分析：最多能拦截的导弹就是最长不上升子序列，导弹系统要拦截的是其实就是最长不下降子序列。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e6+7;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    int n=0,a[maxn];
    int dp[maxn];
     
    int main()
    {
        while(scanf("%d",&a[n])!=EOF) n++;
        int ans=-inf;
        fup(i,0,n)
            dp[i]=1;
        fup(i,0,n){
            fup(j,0,i){
                if(a[j]>a[i])
                    dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
        printf("%d\n",ans);
        ans=-inf;
        fup(i,0,n)
            dp[i]=1;
        fup(i,0,n){
            fup(j,0,i){
                if(a[j]<a[i])
                    dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
        printf("%d\n",ans);
        return 0;
    }