HOJ 2985 Wavio Sequence(最长递增子序列以及其O(n*logn)算法)
Wavio Sequence
My Tags (Edit)
Source : UVA
Time limit : 1 sec Memory limit : 32 M
Submitted : 296, Accepted : 123
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 multiple 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
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
Sample Output
9
9
1
解法是将数组正着和倒着分别求一下最长递增子序列,然后遍历i,如果i左边的数组和右边的数组的最长子序列相等,就是符合条件的。如果求最长递增子序列用O(N^2)会超时,所以必须用效率高的算法。。关于O(n*logn)算法请参考以下博客
http://blog.csdn.net/dacc123/article/details/50571844
贴上代码
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
int a[10005];
int b[10005];
int c[10005];
int d[10005];
int dp[10005];
int bp[10005];
int n;
int ans;
int search(int num,int l,int r,int *dp)
{
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(num>dp[mid])
l=mid+1;
else
r=mid-1;
}
return l;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[n-i+1]=a[i];
}
//memset(dp,0,sizeof(dp));
dp[1]=a[1];
c[1]=1;
int len=1;
for(int i=2;i<=n;i++)
{
if(a[i]>dp[len])
dp[++len]=a[i];
else
{
int pos=search(a[i],1,len,dp);
dp[pos]=a[i];
}
c[i]=len;
}
bp[1]=b[1];
d[1]=1;
int len2=1;
for(int i=2;i<=n;i++)
{
if(b[i]>bp[len2])
bp[++len2]=b[i];
else
{
int pos=search(b[i],1,len2,bp);
bp[pos]=b[i];
}
d[i]=len2;
}
for(int i=1;i<=n;i++)
{
if(c[i]==d[n-i+1])
ans=max(ans,c[i]*2-1);
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- For Freedom —— 代理篇
- lamp
- maven报错非法字符:\65279 错误
- js效果-多选只能选两项,如果超出自动取消第一次选的
- schema约束和引入
- poj-2236-Wireless Network
- 大话数据结构&ndash;1.基础知识+2.算法
- OC和Java的比较
- RTP-实时协议
- Spring Cloud简介以及版本选择
- Python爬虫6-利用ProxyHandler设置代理服务器
- 运用Python计算Π的多少(大致计算)
- tensorflow 笔记13:了解机器翻译,google NMT,Attention
- 牛客寒假算法基础集训营6 I-wzoi
- 句子相似度_tf/idf
- MySQL 第八篇:ORM框架SQLAlchemy
- 利用ImageOps调整图片的Aspect Ratio(给图片添加borders)
- .NET Core2使用Azure云上的Iot-Hub服务
- OVN实战---《The OVN Load Balancer》翻译
- JDBC(4)-Result结果集
热门文章
- go类型系统
- SpringMVC由浅入深day02_9RESTful支持
- 5 -- Hibernate的基本用法 --4 4 数据库方言
- ios开发之--/System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/ruby: bad interpreter: No such file
- python cookie
- Django 添加应用
- tomcat端口被占用的两个解决方法
- apk反编译看包名什么的
- U盘安装centos6.4:缺少iso 9660映像
- mysqlint类型的长度值mysql在建表的时候int类型后的长度代表什么