菜笔只会 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;
}
Categories: 简单DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

简单DP

HDU 6143 Killer Names

昨天的多校应该是团队合作最失败的一次…… 一开始过题人数最多的那道题许 Read more…

简单DP

POJ 1661 Help Jimmy

好题!!!! 这道题我整整想了一个晚上,怎么说呢,应该还是我从一开始就 Read more…

简单DP

HDU 5074 Hatsune Miku

老实说有点崩溃,一场训练赛,3道dp都没出,两道还是全世界都A了 毫无 Read more…