UVA 10534 - Wavio Sequence LIS

题目大意：

给定一个长度为n的整数序列，求一个最长子序列（不一定为连续），使得该序列的长度为奇数2*k+1，前k+1个数严格递增，后k+1个数严格递减。（严格递增/递减意味着相邻两个数不能相同）

思路：

可以求两次LIS（最长上升子序列），一次是递增的，一次是递减的（其实就是倒着求递增的）

n高达10000，因此LIS要用二分查找来优化时间复杂度为O(nlogn)

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=10000+10; const int INF=0x7fffffff; int data[MAXN],d1[MAXN],g1[MAXN],d2[MAXN],g2[MAXN]; int search(int L,int R,int x,int *g) { while(L