Description:

Wozuinb非常喜欢打炉石传说，但是菜的不行，所以他决定打竞技场来练练手。系统按顺序给出n张卡牌，每张卡牌都有自己的使用消耗a[i]，每次只给出一张，wozuinb可以选择或者弃掉这张牌。每选择一张牌都会按选择顺序放在卡槽中，当
卡槽中放满30张即可组成一套套牌。Wozuinb希望自己的套牌的消耗满足一个平滑的曲线，即30张卡牌都满足第i张卡牌的消耗不小于第 i − 1 i-1 i−1张( i > 1 i>1 i>1)。请你帮助wozuinb看一看，这些卡牌能不能组成想要的套牌，如果能组成输出“yes”，如果不能输出“no”。

Input:

第一行输入一个整数n， 0 &lt; n &lt; 100 0&lt;n&lt;100 0<n<100。
第二行输入一行数字a[i]，每个数字用空格隔开，代表第i张出现的卡牌的消耗。

Output:

输出一行，“yes”或“no”

Sample Input:

5
1 2 3 4 5

Sample Output:

no

题目链接

O(n^2)算法求最长不下降子序列

用lis[i]数组存储从第1个数到第i个数的最长不下降子序列，lis[i]便可以通过lis[i-1]求得

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;

// O(n^2)算法求最长不下降子序列
ll n,a[110],lis[110];       // n为序列长度，a数组存序列，lis数组保存第1~i元素中最长不下降子序列的长度

int main() {
    // 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    // 输出序列长度
    cin >> n;
    // 依次输入序列各元素
    for (int i = 1;i <= n;++i) {
        cin >> a[i];
    }
    // 循环依次求1~i中最长不下降子序列的长度
    for (int i = 1;i <= n;++i) {
        // 将lis[i]初始化为1，因为至少有它本身
        lis[i] = 1;
        // 循环1~i中求已求出最长不下降子序列的最大值
        for (int j = 1;j < i;++j) {
            // 判断序列中第i个元素是否不小于(如果题目要求大于则将>=改为>)第j个元素，并且lis[j]加上第i个元素后是否大于lis[i]
            if (a[i] >= a[j] && lis[j] + 1 > lis[i]) {
                lis[i] = lis[j] + 1;        // 更新lis[i]
            }
        }
    }
    // 循环遍历求lis数组中的最大值
    int len = 0;
    for (int i = 1;i <= n;++i) {
        if (lis[i] > len) {
            len = lis[i];
        }
    }
    // 判断是否符合要求组成一套套牌，并按要求输出
    if (len >= 30) {
        cout << "yes" << endl;
    }
    else {
        cout << "no" << endl;
    }
    return 0;
}

O(nlogn)算法求最长不下降子序列长度
从第一个数开始数，如果遇到大于等于已添加队列内队尾数的数就添加至队尾，否则替换掉已添加队列内第一个大于它的数，循环遍历计数得到结果。

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;

// O(nlogn)算法求最长不下降子序列长度
int n,a[40005],d[40005];  // n为序列长度,a数组为输入原始序列，d[k]表示长度为k的不下降子序列末尾元素的最小值(d数组为单调数组(不会减小(可以相等)))

int main() {
    // 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;       // 输入序列长度
    // 依次输入序列中n个元素
    for (int i = 1;i <= n;++i) {
        cin >> a[i];
    }
    d[1] = a[1];
    int len = 1;    // len表示当前已知的最长子序列的长度(0个元素的时候特判)
    // 现在已知最长不下降子序列长度为1，末尾元素的最小值为序列中第一个元素(a[1])
    // 从2~n循环依次求出前i个元素的最长不下降子序列的长度
    for (int i = 2;i <= n;++i) {
        // 考虑新进来一个元素a[i]
        if (a[i] >= d[len]) {       // 如果这个元素大于等于d[len](如果要求序列严格递增(不能相等)则把>=改为>)
            d[++len] = a[i];        // 直接让这个元素排到后面
        }
        else {                      // 如果这个元素小于d[len]，则a[i]应该替换掉d[len]数组中第一个大于a[i]的元素
            int j = upper_bound(d + 1, d + len + 1, a[i]) - d;  // 用STL upper_bound 找出d[len]中第一个大于a[i]的元素
            d[j] = a[i];    // 替换掉
        }
    }
    // 判断是否符合要求组成一套套牌，并按要求输出
    if (len >= 30) {
        cout << "yes" << endl;
    }
    else {
        cout << "no" << endl;
    }
    return 0;
}