枚举每一个是否可以作为以当前这个数为结尾的上升子序列的 倒数第二个数

$O(N^2)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    scanf ("%d", &n);

    for (int i = 1; i <= n; i ++)
        scanf ("%d", &a[i]);

    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1; // 每个数可以以自己为子序列
        for (int j = 1; j < i; j ++) // 枚举 i 之前的可以把a[i]当做上升子序列结尾的子序列
            if (a[i] > a[j])  // 要满足上升的条件
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0; // 答案可能是以a[1 ~ n]的任意一个为结尾的子序列的长度
    for (int i = 1; i <= n; i ++) res = max(res, f[i]);

    printf ("%d", res);
    return 0;
}

$O(Nlog_2N)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
int a[N], q[N];

int main()
{
    scanf ("%d", &n);

    for (int i = 0; i < n; i ++) scanf ("%d", &a[i]);

    int len = 0;
    q[0] = -2e9; // 保证可以找到比a[i]小的数
    for (int i = 0; i < n; i ++)
    {
        int l = 0, r = len;
        while (l < r) // 找到比a[i]小的最大的数
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1); // 因为r + 1的位置上要放一个新的数
        q[r + 1] = a[i]; // 更新一下q[r + 1]
    }

    printf ("%d", len);
    return 0;
}

登山

模型:找到一个点$i$,使得$1 - i$的上升子序列的长度 $+$ $i - n$的下降子序列的长度最大

友好城市

思路:先把一边的点按坐标排序, 然后取另一边的一个上升子序列即为答案,所以我们要找另一边的最长升上子序列即可

导弹拦截

$query.one$求最大的单调不升子序列的长度

$query.two$求整个序列中单调不升子序列的个数

思路(贪心):对于每个拦截系统,我们只记录它们当前拦截的导弹的最低高度,且我们将它们按这个值升序排列,那么我们每次遇到一个新的导弹,我们只需要找到拦截系统的最低高度中大于等于当前导弹的最小值,然后把它接在这个导弹的和后面即可

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N], q[N];

int main()
{
    while (scanf ("%d", &a[n]) != EOF) n ++;

    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++)
            if (a[j] >= a[i])
                f[i] = max(f[i], f[j] + 1);

        res = max(res, f[i]);
    }

    printf ("%d\n", res);

    int cnt = 0, k;
    for (int i = 0; i < n; i ++)
    {
        k = 0;
        // 找到大于等于当前导弹高度的拦截系统最小可用高度
        while (k < cnt && q[k] < a[i]) k ++;
        q[k] = a[i];
        if (k >= cnt) cnt ++;
    }

    printf ("%d", cnt);
    return 0;
}

导弹防御系统

思路:dfs爆搜,对于每一个点用两种决策情况:加在上升子序列中 $or$ 加在下降子序列中

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 55;

int n;
int a[N];
int up[N], down[N];
int res;

void dfs(int u, int su, int sd)
{
    if (su + sd >= res) return ;

    if (u == n + 1)
    {
        res = su + sd;
        return ;
    }

    // 第一种情况:接在最长上升子序列中
    int k = 0;
    // 找到大于等于当前导弹高度的最小高度
    while (k < su && up[k] < a[u]) k ++;
    int t = up[k]; // dfs前要先记录一下,方便回溯
    up[k] = a[u];
    if (k >= su) dfs(u + 1, su + 1, sd);
    else dfs(u + 1, su, sd);
    up[k] = t;

    // 第二种情况:接在最长下降子序列中
    k = 0;
    // 找到小于等于当前导弹高度的最大高度
    while (k < sd && down[k] > a[u]) k ++;
    t = down[k];
    down[k] = a[u];
    if (k >= sd) dfs(u + 1, su, sd + 1);
    else dfs(u + 1, su, sd);
    down[k] = t;
}

int main()
{
    while (scanf ("%d", &n), n)
    {
        for (int i = 1; i <= n; i ++) scanf ("%d", &a[i]);

        res = n;   
        dfs(1, 0, 0);

        printf ("%d\n", res);
    }
    return 0;
}

最长公共上升子序列

思路:考虑到$a[i]$和$b[j]$时,$f[i][j]$表示以$b[j]$为结尾的最长上升公共子序列,再划分集合

1. 不考虑$a[i]$, $f[i][j] = f[i - 1][j]$

2. 若$a[i] == b[j]$,则考虑$a[i]$, 再根据公共上升子序列中倒数第二个数进行划分,求其中的最大值

   • 空
   • $b[1]$ $f[i][j] = f[i - 1][1] + 1$
   • $b[2]$ $f[i][j] = f[i - 1][2] + 1$
   • $···$
   • $b[j - 1]$ $f[i][j] = f[i - 1][j - 1] + 1$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 3030;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    scanf ("%d", &n);

    for (int i = 1; i <= n; i ++) scanf ("%d", &a[i]);
    for (int i = 1; i <= n; i ++) scanf ("%d", &b[i]);

    for (int i = 1; i <= n; i ++)
    {
        // maxv表示a[i] > b[1 ~ j]条件下的f[i - 1][j] + 1的前缀最大值
        int maxv = 1;
        for (int j = 1; j <= n; j ++)
        {
            // 不考虑a[i]点
            f[i][j] = f[i - 1][j];
            // 如果a[i] == b[j]才会去考虑a[i]点
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++) res = max(res, f[n][i]);

    printf ("%d", res);
    return 0;
}