多校联合练习赛1 Problem1005 Deque LIS+LDS 再加一系列优化 (二)
um[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::iterator,vector::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 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;
}
| 评论 |
|
|