uva10534---Wavio Sequence
发布日期:2022-02-02 02:58:14 浏览次数:2 分类:技术文章

本文共 2311 字,大约阅读时间需要 7 分钟。


Wavio is a sequence of integers. It has some interestingproperties.

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

·  The first (n+1) integers ofWavio sequence makes a strictly increasing sequence.

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

·  No two adjacent integers are same in aWavio sequence.

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

1 2 3 2 1 2 3 4 32 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 outputwill be 9.

 

Input

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

 

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

 

Output

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

Sample Input                                  Output for 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
 
9
9
1

 


这道题主要是LIS的应用,把串正反走一遍就行,代码中LIS()函数是精华。

代码实现:

#include 
   
    #include 
    
     using namespace std;#define N 10001int dp1[10001],dp2[10001],a[10001],b[10001];int t;void LIS(int dp[],int a[]){
     
int stack[N];
int top=0;
stack[top]=-99999999;
for(int i=1; i<=t; i++)
{
//如果a[i]>栈顶部元素,则压栈
if(a[i]>stack[top])
{
stack[++top]=a[i];
dp[i]=top;
}
//如果a[i]不大于栈顶部元素,则二分查找第一个比a[i]大的元素
else
{
int l=1,r=top;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[i]>stack[mid])
{
l=mid+1;
}
else
r=mid-1;
}
//替换a[i]
stack[l]=a[i];
dp[i]=l;
}
}}int main(){
while(cin>>t)
{
for(int i=1;i<=t;i++)
{
   cin>>a[i];
   b[t-i+1]=a[i];
}
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
LIS(dp1,a);
LIS(dp2,b);
int maxx=-1,ans=0;
for(int i=1;i<=t;i++)
{
ans=min(dp1[i],dp2[t-i+1])*2-1;
if(ans>maxx)
{
maxx=ans;
}
}
cout< <
}
return 0;}


转载地址:https://blog.csdn.net/u010368749/article/details/22100453 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hdu1087---Super Jumping! Jumping! Jumping!
下一篇:JVM原理

发表评论

最新留言

不错!
[***.249.68.14]2022年05月22日 15时44分02秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

iPhone开发【十五】多线程开发之NSThread——异步下载图片 2019-07-26 18:46:19
iPhone开发【十四】多线程开发之NSThread——子线程模拟耗时操作 2019-07-26 18:46:18
iPhone开发【十三】动画效果之最简单的动画——动态加载图片 2019-07-26 18:46:18
iPhone开发【十二】多视图技术总结之四:Segmented Control 2019-07-26 18:46:17
iPhone开发【十一】多视图技术总结之四:Page Control 2019-07-26 18:46:16
setValue:forUndefinedKey:]: this class is not key value coding-compliant for the key 2019-07-26 18:46:16
[UIView numberOfComponentsInPickerView:]: unrecognized selector sent to instance 2019-07-26 18:46:15
NSMutableArray的正确释放 2019-07-26 18:46:15
如何禁用 UITableView 的高亮选取? 2019-07-26 18:46:14
Mac mini 历险记 —— Mac 黑屏 风扇异响 2019-07-26 18:46:14
IOS 中 赋值、copy、MutableCopy的区别 2019-07-26 18:46:13
IOS 使用UITextField自动格式化银行卡号 2019-07-26 18:46:13
IOS Prefix.pch 文件无法引入.h头文件 2019-07-26 18:46:12
恩与爱是扯不开的 —— 李安 2019-07-26 18:46:12
加班引发的思考…… 2019-07-26 18:46:12
UIImageView 支持点击事件 2019-07-26 18:46:11
iOS学习之iOS沙盒(sandbox)机制和文件操作之NSFileManager(三) 2019-07-26 18:46:11
iOS学习之iOS沙盒(sandbox)机制和文件操作(二) 2019-07-26 18:46:10
iOS学习之iOS沙盒(sandbox)机制和文件操作(一) 2019-07-26 18:46:10
Mac 下搭建Android开发环境 2019-07-26 18:46:09