UVa 10534 波浪子序列（快速求LIS）

题意：
给定一个长度为n的整数序列，求一个最长子序列（不一定连续），使得该序列的长度为2k+1，前k+1个数严格递增，后k+1个数严格递减。

思路：

先正着求一遍LIS，再反着求一遍LIS。

当然求法是得采用O（nlogn）的求法，这个网上有很多解释，我就不多介绍了。

最后的话枚举一遍就可以了，详见代码。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long LL;

 typedef pair<int,int> pll;

 const int INF=0x3f3f3f3f;

 const int maxn=+;

 int n;

 int a[maxn],r_a[maxn],g[maxn],d1[maxn],d2[maxn];

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     while(~scanf("%d",&n))

     {

         for(int i=;i<n;i++)

         {

             scanf("%d",&a[i]);

             r_a[n-i-]=a[i];

         }

         int ans1=;

         for(int i=;i<=n;i++)  g[i]=INF;

         for(int i=;i<n;i++)

         {

             int k=lower_bound(g+,g+n+,a[i])-g;

             d1[i]=k;   //记录了前i个数的最长子序列

             g[k]=a[i];

             ans1=max(ans1,d1[i]);

         }

         int ans2=;

         for(int i=;i<=n;i++)  g[i]=INF;

         for(int i=;i<n;i++)

         {

             int k=lower_bound(g+,g+n+,r_a[i])-g;

             d2[i]=k;

             g[k]=r_a[i];

             ans2=max(ans2,d2[i]);

         }

         //枚举递增和递减的分隔点

         int ans=;

         for(int i=;i<n;i++)

         {

             int temp=min(d1[i],d2[n-i-]);

             temp=*(temp-)+;

             if(ans<temp)  ans=temp;

         }

         printf("%d\n",ans);

     }

     return ;

 }