Menu
Article ACM

SHU 418 A序列

NodeKey

NodeKey

• 2 min read

菜笔只会 O( n ^ 2 ) 的 LIS 的求法，现在补上……其实也非常好理解

这道题我记得很久很久之前就做过原题了，只要求两遍 LIS 即可，但是本来今天就OJ就很卡，好不容易交了两发，本以为两发都 WA 了 ，结果一发 waiting ，一发RE……

这里补上代码以备模板之需

题意：
找出左边递增右边递减，长度相同的子序列。

思路：
两遍LIS，同位置求最小。

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 5e+5;
int ary[maxn], st[maxn];
int dl[maxn], dr[maxn];

int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%d", ary + i);
        memset(st, 0, sizeof st);
        st[1] = ary[0], dl[0] = dr[n - 1] = 1;
        int len = 1, pos;
        for (int i = 0; i < n; i++) {
            pos = lower_bound(st, st + len, ary[i]) - st;
            st[pos] = ary[i];
            len = max(len, pos + 1);
            dl[i] = pos;
        }
        memset(st, 0, sizeof st);
        st[1] = ary[n - 1], len = 1;
        for (int i = n - 1; i >= 0; i--) {
            pos = lower_bound(st, st + len, ary[i]) - st;
            st[pos] = ary[i];
            len = max(len, pos + 1);
            dr[i] = pos;
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, 2 * min(dl[i], dr[i]) - 1);
        printf("%d\n", ans);
    }
}

附上模板

int LIS()
{
    memset(dp, 0, sizeof(int)*n);
    int len = 1;
    dp[0] = a[0];
    for (int i = 1; i < n; ++i)
    {
        int pos = lower_bound(dp, dp + len, a[i]) - dp; //pos 为当前位置的最大上升子序列的长度
        dp[pos] = a[i];
        len = max(len, pos + 1);
    }
    return len;
}
Share