首页 > 其他 > 详细

HDOJ 4604 Deque

时间:2014-03-09 08:28:15      阅读:497      评论:0      收藏:0      [点我收藏+]




Deque

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2054    Accepted Submission(s): 746


Problem Description
Today, the teacher gave Alice extra homework for the girl weren‘t attentive in his class. It‘s hard, and Alice is going to turn to you for help.
The teacher gave Alice a sequence of number(named A) and a deque. The sequence exactly contains N integers. A deque is such a queue, that one is able to push or pop the element at its front end or rear end. Alice was asked to take out the elements from the sequence in order(from A_1 to A_N), and decide to push it to the front or rear of the deque, or drop it directly. At any moment, Alice is allowed to pop the elements on the both ends of the deque. The only limit is, that the elements in the deque should be non-decreasing.
Alice‘s task is to find a way to push as many elements as possible into the deque. You, the greatest programmer, are required to reclaim the little girl from despair.
 

Input
The first line is an integer T(1≤T≤10) indicating the number of test cases.
For each case, the first line is the length of sequence N(1≤N≤100000).
The following line contains N integers A1,A2,…,AN.
 

Output
For each test case, output one integer indicating the maximum length of the deque.
 

Sample Input
3 7 1 2 3 4 5 6 7 5 4 3 2 1 5 5 5 4 1 2 3
 

Sample Output
7 5 3
 

Source
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<int>::iterator VI;

const int maxn=110000;
const int INF=0x3f3f3f3f;

int a[maxn],n,dp1[maxn],dp2[maxn],num1[maxn],num2[maxn];

void doit(int dp[],int num[])
{
    memset(dp,0,sizeof(dp));
    memset(num,0,sizeof(num));

    vector<int> g; g.clear();
    int sz=0;

    for(int i=n-1;i>=0;i--)
    {
        if(!sz||g[sz-1]<=a[i])
        {
            g.push_back(a[i]); sz++;
            dp[i]=sz;
        }
        else
        {
            VI item;

            item=upper_bound(g.begin(),g.end(),a[i]);
            dp[i]=item-g.begin()+1;
            *item=a[i];
        }
        pair<VI,VI> bound=equal_range(g.begin(),g.end(),a[i]);
        num[i]=bound.second-bound.first;
    }
}

int main()
{
    int T,ans;
    scanf("%d",&T);
while(T--)
{
    scanf("%d",&n);
    ans=1;

    for(int i=0;i<n;i++) scanf("%d",a+i);
    doit(dp1,num1);

    for(int i=0;i<n;i++) a[i]*=-1;

    doit(dp2,num2);

    for(int i=0;i<n;i++)
    {
        ans=max(ans,dp1[i]+dp2[i]-min(num1[i],num2[i]));
    }

    printf("%d\n",ans);
}
    return 0;
}



HDOJ 4604 Deque,布布扣,bubuko.com

HDOJ 4604 Deque

原文:http://blog.csdn.net/u012797220/article/details/20807865

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!