To boldly go where no one has gone before.

【学习笔记】最长单调子序列问题

2019-01-31 17:06:44


例题有 P1020 导弹拦截 以及 P1439 最长公共子序列 两道题。

$O(nlogn)$算法

记住函数$upper\_bound()$和$lower\_bound()$,这俩玩意儿查起东西来特别快,复杂度$O(logn)$。$upper\_bound()$查询的是从区间内第一个大于查找值的指针,而$lower\_bound()$则是第一个大于等于查找值的指针。同时,前面加上* 就可以直接访问指针指向的地址,这个和迭代器很像。按如下方式重载$cmp$之后可以直接查询不等号取反的值:

bool cmp(int a, int b) {
    return a > b;
}

或者是

struct cmp{
    bool operator () (int a, int b) {
        return a > b;
    }
};

真是太好用了,不过要记住的是重载$cmp$的时候一定要写大于号。$sort$重载$cmp$后排列顺序同$cmp$函数返回时采用的不等号,这里理解为两个查找函数都是先把原序列$O(logn)$快排预处理,而预处理是采用升序排序,因此重载的时候要写大于符号。最后$O(logn)$二分查找,如果没有查找到将返回$last$指针。

$e.g.$ 求最长上升子序列标程

dp[1] = num[1];
for(int i=2; i<=n; i++) {
    if(num[i] > dp[cnt])
        dp[++cnt] = b[i];
    else
        *upper_bound(dp+1, dp+cnt+1, num[i], cmp) = num[i];
}

可以简单理解为用$upper\_bound()$优化的贪心算法,用$dp[cnt]$维护当前状态下子序列最后一个元素的最小值,$cnt$维护当前状态下子序列的最大长度,如果枚举到的数字比当前子序列的最后一个元素大,那么就把最后一个元素换为枚举到的数字,并且$cnt$++,这样就能使尽量多的数字能被包含在子序列当中 (即$cnt$尽量大)。否则就用$upper\_bound()$查第一个大于当前枚举数字的元素,然后把它换成自己,这样就能保证$dp[cnt]$尽可能地小,从而找到最长的上升子序列。

如果是最长不下降子序列问题,直接把$upper\_bound()$换成$lower\_bound()$即可,如果是最长不上升/下降子序列问题则直接重载$cmp$即可。最长不上升/不下降序列问题还需将贪心中的不等号改成$\le$或$\ge$

导弹拦截问题

最多能拦截多少枚导弹则是求最长不上升子序列长度,需配备多少套系统则是求最长上升子序列长度。两算法并行,最后直接输出长度即可。

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;

int missle[MAXN];
int mx[MAXN], lst[MAXN];
int mxcnt = 1, lstcnt = 1;

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    int n = 1;
    while(cin >> missle[n])
        n++;
    n--;
    mx[1] = lst[1] = missle[1];
    for(int i=2; i<=n; i++) {
        if(mx[mxcnt] >= missle[i])
            mx[++mxcnt] = missle[i];
        else
            *upper_bound(mx+1, mx+mxcnt+1, missle[i], cmp) = missle[i];
        if(lst[lstcnt] < missle[i])
            lst[++lstcnt] = missle[i];
        else
            *lower_bound(lst+1, lst+lstcnt+1, missle[i]) = missle[i];
    }
    cout << mxcnt << " " << lstcnt;
    return 0;
}

最长公共子序列问题

把第一个序列当中的数字按照顺序重新标号,然后把第二序列中的数字用得到的标号重新对应,得到一个新的序列,再直接对这个序列求一次最长上升/不下降子序列即可。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100010;
int a[MAXN], num[MAXN], b[MAXN], n, x;
int cnt = 1, dp[MAXN];

int main() {
    memset(dp, 0, sizeof(dp));
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        num[a[i]] = i;
    }
    for(int i=1; i<=n; i++) {
        cin >> x;
        b[i] = num[x];
    }
    dp[1] = b[1];
    for(int i=2; i<=n; i++) {
        if(b[i] > dp[cnt])
            dp[++cnt] = b[i];
        else
            *upper_bound(dp+1, dp+cnt+1, b[i]) = b[i];
    }
    cout << cnt;
    return 0;
}

$O(n^2)$算法

有些时候,数据太小,可以直接用$O(n^2)$的暴力算法水过去。说白了$O(nlogn)$算法实质上就是对$O(n^2)$算法的优化,通过二分/使用数据结构/套$\text{STL}$等操作压出一个$log$来。因此还是有必要掌握最基础的暴力$\text{dp}$方法的。

例题 P1108

这道题实质上就是求最长下降子序列的长度,以及字典序不同的最长下降子序列的个数为多少。

我一看,哇,$N\leq5000$,那就可以用$O(n^2)$算法水掉了。用$dp[i]$维护以$a[i]$结尾的最长下降子序列长度,$dp2[i]$维护以$a[i]$为结尾的最长下降子序列的个数。

首先跑一遍最长下降子序列的$\text{dp}$,然后遍历之前的$dp[j]$,考虑如何进行决策:如果之前有个数和他一样,而且以那个数结尾的最长下降子序列长度和现在一样,那么就找到了一种和当前重复的方案,直接把$dp2[i]$设为$0$即可去重;否则,如果这两个数恰好可以构成一个最长下降子序列,那么就可以把$dp2[i]$的信息转移到$dp2[j]$上;还有个小细节,如果没法找到满足条件的数,那么就意味着可以把$a[i]$作为一个新序列的第一个数,直接$dp2[i]=1$即可。这样就完成了一次决策。

决策完成之后,即可统计$dp[i]=maxlen$的所有方案(即最长子序列的个数),输出即可。

这就涉及到了$\text{dp}$的核心:完成决策。如果单纯地考虑如何进行状态转移,那么是无法准确地描述出整个过程的。反之,如果考虑该如何进行每一次决策(即如何利用前驱状态计算出后继状态),那么就可以思路清晰地完成算法设计。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
int n, a[MAXN];
int dp[MAXN], dp2[MAXN];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    dp[1] = 1;
    int maxlen = 0;
    for(int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for(int j = 1; j < i; j++)
            if(a[i] < a[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        maxlen = max(dp[i], maxlen);
        for(int j = 1; j < i; j++)
        {
            if(dp[i] == dp[j] && a[i] == a[j])
                dp2[j] = 0;
            else
                if(dp[i] == dp[j] + 1 && a[i] < a[j])
                    dp2[i] += dp2[j];
        }
        if(!dp2[i])
            dp2[i] = 1;
    }
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        if(dp[i] == maxlen)
            sum += dp2[i];
    }
    printf("%d %d", maxlen, sum);
    return 0;
}