UVA 10534

题意：

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

1）它的长度总为奇数，即 2*n+1；

2）前(n+1) 个数构成一个严格的上升序列，后(n+1)个数构成一个严格下降的序列；

3）任意相邻两个数不会相同

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

 

解题：

对于每个数， 求出它前面有多少数比他小，后面有多少数比他大，

两者取小，再乘2减1，然后就可以得到以这个点为中心Wavio序列的长度；

从前往后求一次LIS，再从后往前求一次；

因为d[i]表示到下标为 i 的数时LIS的长度；在第二次求的时候可以直接取小

最后循环一遍答案就是 ans = max(ans, d[i]*2-1);

用n^2的方法求LIS会超时，要用n*logn的方法求。

先开始想了半天递推没想出来呢= =

 

#include 
     
      #define ll long longusing 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(){  //  freopen("in.txt", "r", stdin);  //  freopen("out.txt", "w", stdout);    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;}