最长上升子序列

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

若 \(n=0\)，则需要特判。 # 最长上升子序列

目前我笔记有三种写法，第一种即可。 推荐 1

#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;
}

推荐 2

#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(); 
}

推荐 3

#include <bits/stdc++.h>//边输入边计算，有时不适用
using namespace std;
vector<int> d;
int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        auto it = lower_bound(d.begin(), d.end(), t);
        if (it != d.end())
            *it = t;
        else
            d.push_back(t);
    }
    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;
}