首页 > 代码库 > BNUOJ 14381 Wavio Sequence

BNUOJ 14381 Wavio Sequence

Wavio Sequence

Time Limit: 3000ms
Memory Limit: 131072KB
This problem will be judged on UVA. Original ID: 10534
64-bit integer IO format: %lld      Java class name: Main
 

Wavio is a sequence of integers. It has some interesting properties.

  Wavio is of odd length i.e. L = 2*n + 1.

  The first (n+1) integers of Wavio sequence makes a strictly increasing sequence.

  The last (n+1) integers of Wavio sequence makes a strictly decreasing sequence.

  No two adjacent integers are same in a Wavio sequence.

For example 1, 2, 3, 4, 5, 4, 3, 2, 0 is an Wavio sequence of length 9. But 1, 2, 3, 4, 5, 4, 3, 2, 2 is not a valid wavio sequence. In this problem, you will be given a sequence of integers. You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence. Consider, the given sequence as :

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1.


Here the longest Wavio sequence is : 1 2 3 4 5 4 3 2 1. So, the output will be 9.

 

Input

The input file contains less than 75 test cases. The description of each test case is given below: Input is terminated by end of file.

 

Each set starts with a postive integer, N(1<=N<=10000). In next few lines there will be N integers.

 

Output

For each set of input print the length of longest wavio sequence in a line.

 

Sample Input

10

1 2 3 4 5 4 3 2 1 10

19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

5

1 2 3 4 5


Sample Output

9

9

1

解题:最长上升子序列加强版。单调队列优化!!!重点。先顺着求最长上升子序列,再逆着求最长上升子序列。


 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 10100;18 int dp1[maxn],dp2[maxn],d[maxn],q[maxn];19 int bsearch(int lt,int rt,int val) {20     while(lt <= rt) {21         int mid  = (lt+rt)>>1;22         if(q[mid] < val) lt = mid+1;//严格上升单调取少于符号,上升的取少于等于23         else rt = mid-1;24     }25     return lt;26 }27 int main() {28     int n,i,j,head,tail;29     while(~scanf("%d",&n)) {30         for(i = 0; i < n; i++)31             scanf("%d",d+i);32         head = tail = 0;33         for(i = 0; i < n; i++) {34             if(head == tail) {35                 q[head++] = d[i];36                 dp1[i] = head-tail;37             }else if(d[i] > q[head-1]){38                 q[head++] = d[i];39                 dp1[i] = head-tail;40             }else{41                 int it = bsearch(tail,head-1,d[i]);42                 dp1[i] = it - tail + 1;43                 q[it] = d[i];44             }45         }46         head = tail = 0;47         for(i = n-1; i >= 0; i--) {48             if(head == tail) {49                 q[head++] = d[i];50                 dp2[i] = head-tail;51             }else if(d[i] > q[head-1]){52                 q[head++] = d[i];53                 dp2[i] = head-tail;54             }else{55                 int it = bsearch(tail,head-1,d[i]);56                 dp2[i] = it - tail + 1;57                 q[it] = d[i];58             }59         }60         int ans = 1;61         for(i = 0; i < n; i++){62             ans = max(ans,min(dp1[i],dp2[i])*2-1);63         }64         printf("%d\n",ans);65     }66     return 0;67 }
View Code