Wavio Sequence
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int inf=0x3f3f3f3f; 6 7 int main() 8 { 9 int n; 10 int a[10005],b[10005]; 11 int dp1[10005],dp2[10005],num1[10005],num2[10005],num3[10005]; 12 int i,j,k; 13 while(scanf("%d",&n)!=EOF) 14 { 15 for(i=0;i<n;i++) 16 { 17 scanf("%d",&a[i]); 18 } 19 for(i=0;i<n;i++) 20 { 21 dp1[i]=inf; 22 dp2[i]=inf; 23 } 24 25 for(i=0;i<n;i++) 26 b[n-i-1]=a[i]; 27 28 for(i=0;i<n;i++) 29 { 30 int lower; 31 lower=lower_bound(dp2,dp2+n,a[i])-dp2; 32 num2[i]=lower+1; 33 dp2[lower]=a[i]; 34 35 lower=lower_bound(dp1,dp1+n,b[i])-dp1; 36 num3[i]=lower+1; 37 dp1[lower]=b[i]; 38 } 39 40 for(i=0;i<n;i++) 41 num1[n-i-1]=num3[i]; 42 43 /*for(i=0;i<n;i++) 44 { 45 printf("%d ",num1[i]); 46 }*/ 47 48 int ans=1; 49 for(i=0;i<n;i++) 50 { 51 int mi=min(num1[i],num2[i]); 52 if(mi>ans) 53 ans=mi; 54 } 55 printf("%d ",ans*2-1); 56 } 57 return 0; 58 }