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

1 2 3 4 5 4 3 2 1 10

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

1 2 3 4 5

Sample Output


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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 int dp1[maxn],dp2[maxn],d[maxn],q[maxn];

 int bsearch(int lt,int rt,int val) {

     while(lt <= rt) {

         int mid  = (lt+rt)>>;

         if(q[mid] < val) lt = mid+;//严格上升单调取少于符号，上升的取少于等于

         else rt = mid-;

     }

     return lt;

 }

 int main() {

     int n,i,j,head,tail;

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

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

             scanf("%d",d+i);

         head = tail = ;

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

             if(head == tail) {

                 q[head++] = d[i];

                 dp1[i] = head-tail;

             }else if(d[i] > q[head-]){

                 q[head++] = d[i];

                 dp1[i] = head-tail;

             }else{

                 int it = bsearch(tail,head-,d[i]);

                 dp1[i] = it - tail + ;

                 q[it] = d[i];

             }

         }

         head = tail = ;

         for(i = n-; i >= ; i--) {

             if(head == tail) {

                 q[head++] = d[i];

                 dp2[i] = head-tail;

             }else if(d[i] > q[head-]){

                 q[head++] = d[i];

                 dp2[i] = head-tail;

             }else{

                 int it = bsearch(tail,head-,d[i]);

                 dp2[i] = it - tail + ;

                 q[it] = d[i];

             }

         }

         int ans = ;

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

             ans = max(ans,min(dp1[i],dp2[i])*-);

         }

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

     }

     return ;

 }

巴特西

BNUOJ 14381 Wavio Sequence

Wavio Sequence

Sample Input

Sample Output

最新文章

热门文章