UVa 10534 - Wavio Sequence

链接

传送门

题意

给出数列${a_i}$输出最长的长度为$2n+1$的前$n$项严格递增,后$n$项严格递减的子序列的长度。

思路

求两边LIS,枚举每个点的上升前缀$d1_i$和下降后缀$d2_i$,答案为$max(min(d1_i,d2_i)*2-1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 10010;
int a[maxn], g[maxn], d1[maxn], d2[maxn];
int main() {
int n;
while (~scanf("%d", &n)) {
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
fill(g, g + n + 1, inf);
for (int i = 0; i < n; ++i) {
int k = int(lower_bound(g + 1, g + n + 1, a[i]) - g);
d1[i] = k;
g[k] = a[i];
}
fill(g, g + n + 1, inf);
for (int i = n - 1; i >= 0; --i) {
int k = int(lower_bound(g + 1, g + n + 1, a[i]) - g);
d2[i] = k;
g[k] = a[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, (min(d1[i], d2[i]) << 1) - 1);
}
printf("%d\n", ans);
}
return 0;
}

支付宝扫码领红包