UVa 10534 - Wavio Sequence

链接

传送门

题意

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

思路

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

代码

#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;
}