标签：10534 int 题解 len maxn LIS 序列 Wavio

题目传送门

---

题意

\(Wavio\) 是整数序列，有如下特点：

1. 它的长度总为奇数，即 \(2n + 1\)；
2. 前 \(n+1\) 个数构成一个严格的上升序列，后 \(n+1\) 个数构成一个严格下降的序列；
3. 任意相邻两个数不会相同

多组输入，给出 \(n\)，接下来 \(n\) 个数，求此数列中 \(Wavio\) 序列的最大长度。

---

分析

对于每个数， 求出它前面有多少数比他小，后面有多少数比他大，
两者取小，再乘 \(2\) 减 \(1\)，然后就可以得到以这个点为中心 \(Wavio\) 序列的长度；

从前往后求一次 LIS，再从后往前求一次；
因为 \(d_i\) 表示到下标为 \(i\) 的数时 LIS 的长度；在第二次求的时候可以直接取小

最后循环一遍答案就是 \(ans = max(ans, d_i \times 2-1)\);

用 \(n^2\) 的方法求 LIS 会超时，要用 \(n \times \log n\) 的方法求。

\(Code\)

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

const int maxn = 10010;
const int INF = 0x3f3f3f3f;

int d[maxn], a[maxn], h[maxn];

int BFind(int c[], int len, int x)
{
    int l = 0, r = len, mid;
    while (l <= r) {
        mid = (l+r)/2;
        if (x < c[mid]) r -= 1;
        else if (x > c[mid]) l += 1;
        else return mid;
    }
    return l;
}

int main()
{
    int n;
    while (scanf ("%d", &n) != EOF) {
        memset (h, 0, sizeof (h));
        for (int i = 1; i <= n; i ++)
            scanf ("%d", &a[i]);
        int len = 1;
        h[0] = -INF; h[1] = a[1];
        for (int i = 1; i <= n; i ++) {
            int x = BFind(h, len, a[i]);
            h[x] = a[i];
            len = max (len, x);
            d[i] = len;
        }
        h[0] = -INF; h[1] = a[n]; len = 1;
        for (int i = n; i >= 1; i --) {
            int x = BFind(h, len, a[i]);
            h[x] = a[i];
            len = max (len, x);
            d[i] = min(d[i], len);
        }
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            ans = max (ans , d[i] * 2 - 1 );
        }
        printf ("%d\n", ans );
    }
    return 0;
}

标签：10534,int,题解,len,maxn,LIS,序列,Wavio
From： https://www.cnblogs.com/mrCrazyWolf/p/16928405.html