(DP6.1.4.3)UVA 10534 Wavio Sequence(利用二分查找来富足DP)

 
/* 
 * UVA_10534.cPP 
 * 
 *  Created on: 2013年10月13日 
 *      Author: Administrator 
 */  
  
#include   
#include   
#include   
#include   
#include   
  
using namespace std;  
  
const int maxn = 10010;  
int n,A[maxn],L[maxn],F[maxn],G[maxn];  
  
int binary( int x){  
    int mid ;  
  
    int l = 0 ;  
    int r = n;  
    while(l < r){  
        mid =  (l + r)/2;  
        if(L[mid+1] >= x){  
            r = mid;  
        }else{  
            l = mid + 1;  
        }  
    }  
  
    return l;  
}  
  
  
int main(){  
    while(scanf("%d",&n)!=EOF){  
  
        int i;  
  
        for(i = 1 ; i <= n ; ++i){  
            scanf("%d",&A[i]);  
        }  
  
        for(i = 1 ; i <= n ; ++i){  
            L[i] = 2147483647;  
        }  
        L[0] = -2147483647 - 1;  
  
        for(i = 1 ; i <= n ; ++i){  
            F[i] = binary(A[i]) + 1;  
  
            if(A[i] < L[F[i]]){  
                L[F[i]] = A[i];  
            }  
        }  
  
        for(i = 1 ; i <= n ; ++i){  
            L[i] = 2147483647;  
        }  
        L[0] = -2147483647 - 1;  
  
        for(i = n ; i >





= 1 ; --i){  
            G[i] = binary(A[i]) + 1;  
  
            if(A[i] < L[G[i]]){  
                L[G[i]] = A[i];  
            }  
        }  
  
        int ans = 0;  
        for(i = 1 ; i <= n ; ++i){  
            int k = min(F[i],G[i]);  
            if(ans < k){  
                ans = k;  
            }  
        }  
  
        printf("%d\n",ans*2-1);  
//      cout<