(DP6.1.4.3)UVA 10534Wavio Sequence(利用二分查找来富足DP)
/* * UVA_10534.cPP * * Created on: 2013年10月13日 * Author: Administrator */#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>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<<ans*2-1<<endl;}return 0;}