uva 10534 Wavio Sequence (LIS)

题意：

找一个最长（假设长度为2N-1）的子序列，使得前N个元素递增，后N个元素递减。

思路：

用nlogn的方法首尾各求一遍LIS,然后枚举中点就可以了。

注意要求中点两边一样长。

代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 1e5+5;int n, a[maxn], b[maxn], dp1[maxn], dp2[maxn];int main(void){    while(cin >> n)    {        for(int i = 1; i <= n; i++)            scanf("%d", &a[i]);        int len = 1, l, r;        b[1] = a[1];        for(int i = 1; i <= n; i++)        {            l = 1, r = len;            while(l <= r)            {                int mid = (l+r)/2;                if(b[mid] < a[i]) l = mid+1;                else r = mid-1;            }            b[l] = a[i];            dp1[i] = l;            if(l > len) len++;        }        b[1] = a[n];        len = 1;        for(int i = n; i >= 1; i--)        {            l = 1, r = len;            while(l <= r)            {                int mid = (l+r)/2;                if(b[mid] < a[i]) l = mid+1;                else r = mid-1;            }            b[l] = a[i];            dp2[i] = l;            if(l > len) len++;        }        int ans = 0;        for(int i = 1; i <= n; i++)            if(min(dp1[i], dp2[i])*2-1 > ans)                ans = min(dp1[i], dp2[i])*2-1;        PRintf("%d/n", ans);    }    return 0;}