题意
\(Wavio\) 是整数序列,有如下特点:
- 它的长度总为奇数,即 \(2n + 1\);
- 前 \(n+1\) 个数构成一个严格的上升序列,后 \(n+1\) 个数构成一个严格下降的序列;
- 任意相邻两个数不会相同
多组输入,给出 \(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