Deque
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 731 Accepted Submission(s): 236
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
2013 Multi-University Training Contest 1
Recommend
liuyiding
我直接附上標准題解吧。。當時是看出這是最長下降跟最長上升序列的求和的，只是因為沒相處nlogn算法，最終沒有做出來。 今天終於AC掉了。 剛開始考慮的時候，還是沒有考慮到
5
5 5 5 5 5 這種需要過濾掉重復的方法，導致WA了很多次，後來多開了一個數組保留才AC掉。
標准題解是：
Problem E. Deque考慮題目的一個簡化版本:使雙端隊列單調上升。對於序列 A 和隊列 Q,找到隊列中最早出現的數字Ax,則Ax將 Q 分成的兩個部分分別是原序列中以Ax開始的最長上升和最長下降序列,答案即為這兩者之和的最大值。而對於本題,由於存在相同元素,所以只要找到以Ax為起點的最長不下降序列和最長不上升序列的和,然後減去兩個裡面出現Ax 次數的最小值即可。
我的代碼是：
/*
* @author ipqhjjybj
* @date 20130723
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 100005
#define clr(x,k) memset((x),(k),sizeof(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n;
int a[MAXN];
int d_p[MAXN]; //存儲遞減序列的數字
int d_f[MAXN];
int n_d_f[MAXN];//相同數字出現次數
int i_p[MAXN]; //存儲遞增序列的數字
int i_f[MAXN];
int n_i_f[MAXN];//相同數字出現次數
int find_dec(int l,int r,int x){
int i=l,j=r,mid;
while(i<=j){
mid=(i+j)>>1;
if(d_p[mid]<=x) i=mid+1;
else j=mid-1;
}return i;
}
int find_inc(int l,int r,int x){
int i = l,j=r,mid;
while(i<=j){
mid=(i+j)>>1;
if(i_p[mid]>=x) i=mid+1;
else j=mid-1;
}return i;
}
int main(){
//freopen("1005.in","r",stdin);
int z;
scanf("%d",&z);
while(z--){
clr(n_i_f,0),clr(n_d_f,0);
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);
int ans=1;
int d_ans=1;
d_p[1]=a[n];
d_f[n]=1;
n_d_f[1]=1;
int i_ans=1;
i_p[1]=a[n];
i_f[n]=1;
n_i_f[1]=1;
for(int i=n-1;i>0;i--){
int t1=find_dec(1,d_ans,a[i]);
if(t1>d_ans)d_ans++;
d_p[t1]=a[i];
n_d_f[t1]=(t1>1&&d_p[t1-1]==a[i])?n_d_f[t1-1]+1:1;
d_f[i]=t1;
int t2=find_inc(1,i_ans,a[i]);
if(t2>i_ans)i_ans++;
i_p[t2]=a[i];
n_i_f[t2]=(t2>1&&i_p[t2-1]==a[i])?n_i_f[t2-1]+1:1;
i_f[i]=t2;
//printf("m_t1=%d m_t2=%d\n",m_t1,m_t2);
int temp = t1+t2-min(n_d_f[t1],n_i_f[t2]);
ans = max(ans,temp);
}
printf("%d\n",ans);
}
return 0;
}
#include "iostream"
#include "cstring"
#include "cstdio"
#include "vector"
#include "algorithm"
#include "map"
using namespace std;
const int N = 100010;
int a[N];
int num_up[N],num_down[N];
int dp_up[N],dp_down[N];
int n;
void getdp(int dp[],int num[])
{
dp[n]=1;
vector<int> v;
v.push_back(a[n]);
vector<int>::iterator iter;
for(int i=n-1;i>=1;i--){
int sz=v.size();
if(a[i]>v[sz-1]){
v.push_back(a[i]);
dp[i]=sz+1;
num[i]=1;
}else if(a[i]==v[sz-1]){
iter=upper_bound(v.begin(),v.end(),a[i]);
dp[i]=iter-v.begin()+1;
v.push_back(a[i]);
pair<vector<int>::iterator,vector<int>::iterator> bounds;
bounds=equal_range(v.begin(),v.end(),a[i]);
num[i]=bounds.second-bounds.first;
}else{
iter=upper_bound(v.begin(),v.end(),a[i]);
dp[i]=iter-v.begin()+1;
*iter=a[i];
pair<vector<int>::iterator,vector<int>::iterator> bounds;
bounds=equal_range(v.begin(),v.end(),a[i]);
num[i]=bounds.second-bounds.first;
}
}
}
void debug(int a[])
{
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
int main(void)
{
int T;
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d",&n);
map<int,int> mp;
mp.clear();
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
getdp(dp_up,num_up);
for(int i=1;i<=n;i++){
a[i]=-a[i];
}
getdp(dp_down,num_down);
for(int i=1;i<=n;i++){
mp[a[i]]++;
ans=max(ans,dp_down[i]+dp_up[i]-min(num_up[i],num_down[i]));
}
printf("%d\n",ans);
}
return 0;
}
