题目描述

blablabla

样例

blablabla

如果只过了9个点 请注意读题，导弹的第二发不能高于第一发，他没说不能等于。
数学的做法是y总的，学的不是很明白。
我是菜逼

朴素做法

(暴力枚举) $O(n^2)$

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 102;
vector<int> v;
int dp1[N] , dp2[N];


int main()
{
    int x,cnt=0,ans=0;
    while(cin>>x)v.push_back(x);

    for(int i = 0; i < v.size(); i ++ ){
        dp1[i]  = 1;
        // 最长非上升
        for(int j = 0; j < i; j ++ )
            if(v[j] >= v[i])
                dp1[i] = max(dp1[i] , dp1[j]+1);
        ans = max(ans , dp1[i]);
    }
    for(int i = v.size()-1; i >= 0; i -- ){
        dp2[i]  = 1;
        // 最长上
        for(int j = v.size()-1; j >i; j -- )
            if(v[j] > v[i])
                dp2[i] = max(dp2[i] , dp2[j]+1);
        cnt = max(cnt , dp2[i]);
    }

    cout<<ans<<endl<<cnt<<endl;
    return 0;
}

数学做法

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int q[N];
int f[N] , g[N];


int main()
{
    while(cin>>q[n]) n++;

    int res = 0 , cnt = 0;
    for(int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(q[j] >= q[i])
                f[i] = max(f[i] , f[j] + 1);
        res = max(res , f[i]);
    }
    cout<<res<<endl; // 最长下降子序列
    for(int i = 0; i < n; i ++ )
    {
        int k = 0;
        while(k < cnt && g[k] < q[i]) k ++ ;
        g[k] = q[i];
        if(k >= cnt) cnt ++ ;
    }
    cout<< cnt <<endl;
    return 0;
}