最长上升子序列

总结推荐写法:

最长上升子序列：lower

void solve() {
	vector<int> d;
    for (auto x : inputArray) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end()){
	        d.push_back(x);
        } else {
	        *it = x;
        }
    }
    cout << d.size() << '\n';
}

最长不下降子序列：upper

void solve() {
	vector<int> d;
    for (auto x : inputArray) {
        auto it = upper_bound(d.begin(), d.end(), x);
        if (it == d.end()){
	        d.push_back(x);
        } else {
	        *it = x;
        }
    }
    cout << d.size() << '\n';
}

最长下降子序列：lower,greater

void solve() {
	vector<int> d;
    for (auto x : inputArray) {
        auto it = lower_bound(d.begin(), d.end(), x, greater());
        if (it == d.end()){
	        d.push_back(x);
        } else {
	        *it = x;
        }
    }
    cout << d.size() << '\n';
}

最长不上升子序列：upper, greater

void solve() {
	vector<int> d;
    for (auto x : inputArray) {
        auto it = upper_bound(d.begin(), d.end(), x, greater());
        if (it == d.end()){
	        d.push_back(x);
        } else {
	        *it = x;
        }
    }
    cout << d.size() << '\n';
}

杂项：

示例
P1020 导弹拦截
用到了求最长下降子序列和最长上升子序列 ，还用到了 $Dilworth\mathrm{定}\mathrm{理}$ 证明第二问是最长上升子序列。

若 $n=0$，则需要特判。
最长上升子序列

最长上升子序列最推荐的写法：从 0 下标开始：

void solve() {
	vector<int> d;
    for (auto x : inputArray) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end()){
	        d.push_back(x);
        } else {
	        *it = x;
        }
    }
    cout << d.size() << endl;
}

#include <bits/stdc++.h>//模板
using namespace std;
vector<int> nums;
vector<int> vec;
int main()
{
    int x;
    cin >> x;
    while(x--)
    {
        int y;
        cin >> y;
        nums.emplace_back(y);
    }
    int n = nums.size();
    
    for (int i = 0; i < n; i++)
    {
        int p = lower_bound(vec.begin(), vec.end(), nums[i]) - vec.begin(); //二分查找，返回大于等于nums[i]的第一个位置
        if (p == vec.size())                                                
            vec.push_back(nums[i]);
        else
            vec[p] = nums[i]; 
    }
    cout<< vec.size(); 
}

#include<bits/stdc++.h>//标准模板
using namespace std;
const int MAXN = N;
int a[MAXN], d[MAXN];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    //if(n==0)//后面不再重复写出
    //{
    //    cout << '0' << endl;
    //    return 0;
    //}
    d[1] = a[1];
    int len = 1;
    for (int i = 2; i <= n;i++)
    {
        if(a[i]>d[len])
            d[++len] = a[i];
        else
        {
            int pos = lower_bound(d + 1, d + 1 + len, a[i]) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
}

最长下降子序列
和上面的代码思路一模一样，稍改

void solve() {
	vector<int> d;
    for (auto x : inputArray) {
        auto it = lower_bound(d.begin(), d.end(), x, greater());
        if (it == d.end()){
	        d.push_back(x);
        } else {
	        *it = x;
        }
    }
    cout << d.size() << endl;
}

#include<bits/stdc++.h>//标准模板
using namespace std;
const int MAXN = N;
int a[MAXN], d[MAXN];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    d[1] = a[1];
    int len = 1;
    for (int i = 2; i <= n;i++)
    {
        if(a[i]<d[len])
            d[++len] = a[i];
        else
        {
            int pos = lower_bound(d + 1, d + 1 + len, a[i],greater<int>()) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
}

最长不下降子序列

#include <bits/stdc++.h>
using namespace std;
const int MAXN = N;
int a[MAXN];
int d[MAXN];

int main()
{
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    if (n == 0) // 0个元素特判一下
    {
        cout<<'0'<<'\n';
        return 0;
    }
    d[1] = a[1]; //初始化
    int len = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= d[len])
            d[++len] = a[i]; 
    //如果可以接在len后面就接上，如果是最长上升子序列，这里变成>
        else//否则就找一个最该替换的替换掉
        {
            int j = upper_bound(d + 1, d + len + 1, a[i]) - d; 
//找到第一个大于它的d的下标，如果是最长上升子序列，这里变成lower_bound
            d[j] = a[i];
        }
    }
    cout<<len<<'\n';
    return 0;
}

最长不上升子序列

#include<bits/stdc++.h>
using namespace std;
const int MAXN = N;
int a[MAXN], d[MAXN];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    if(n==0)
    {
        cout << '0' << endl;
        return 0;
    }
    d[1] = a[1];
    int len = 1;
    for (int i = 2; i <= n;i++)
    {
        if(a[i]<=d[len])
            d[++len] = a[i];
        else
        {
            int pos = upper_bound(d + 1, d + 1 + len, a[i], greater<int>()) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
}

最长不下降子序列的内容

#include <bits/stdc++.h>
using namespace std;
int a[1000010], dp[1000010], poa[1000010],ana[1000010];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dp[1] = a[1];
    int len = 1;
    poa[1] = len;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= dp[len])
        {
            dp[++len] = a[i];
            poa[i] = len;
        }
        else
        {
            int pos = upper_bound(dp + 1, dp + len + 1, a[i]) - dp;
            dp[pos] = a[i];
            poa[i] = pos;
        }
    }
    int t = len;
    for (int i = n; i >=1; i--)
    {
        if (!len)
            break;
        if (poa[i] == len)
            ana[len] = i,len--;
    }
    for (int i = 1; i <= t; i++)
        cout << a[ana[i]] << " ";
}