UVA10534:Wavio Sequence(最长递增和递减序列 n*logn)（LIS)好题
2024-08-23 21:06:47
题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68553#problem/B
题目要求：
Wavio是一个整数序列，具有以下特性：
1、Wavio序列的长度是奇数， 即 L = 2 * n + 1;
2、Wavio序列前 n+1 个整数是递增序列
3、Wavio序列后 n+1 个整数是递减序列
如示例 1 2 3 4 5 4 3 2 1 10
最长的 Wavio序列 为 1 2 3 4 5 4 3 2 1 ，所以答案为9
题目解析：
这题做了一中午，第一次做完之后果断TLE了，第一次的做法是对于序列(1,n)暴力求解，先求出a[i]的最长子序列，再求以a[i]为开始的最长递减序列，注意求递增递减
的二分的边界写法。这时候遍历一遍max(min(a[i]的最长，a[i]的最短）*2-1)，即为所求结果，不幸直接TLE了。
之后一想，可以先求出这个序列的最长子序列，并记录每一个数最长子序列。
同理，再倒序求出序列的最长子序列，并记录每一个数最长子序列。
这时候在遍历一遍每个数，结果即为max(min（a[i]的最长增长子序列，a[i]的最长递减子序列）*2-1)；理由不言而喻。
A了一中午，值得纪念。
AC的：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int n,a[],d[],w[],ad[],ad2[],sum,len,l2;
int er(int q[],int l,int r,int key)//好好研究二分
{
int mid;
while(l<=r)
{
mid=(l+r)/;
if(q[mid]==key)
{
return mid;
}
else if(q[mid]>key)
{
r=mid-;
}
else l=mid+;
}
return l;
}
int main()
{
int we;
while(scanf("%d",&n)!=EOF)
{
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
sum=;
len=;
d[len]=a[];
ad[]=;
for(int i=; i<=n; i++)
{
if(a[i]>d[len])
{
d[++len]=a[i];
ad[i]=len;
}
else
{
we=er(d,,len,a[i]);
d[we]=a[i];
ad[i]=we;
}
}
l2=;
w[l2]=a[n];
ad2[n]=;
for(int i=n-; i>=; i--)
{
if(a[i]>w[l2])
{
w[++l2]=a[i];
ad2[i]=l2;
}
else
{
we=er(w,,l2,a[i]);
w[we]=a[i];
ad2[i]=we;
}
}
for(int i=;i<=n;i++)
{
sum=max(sum,(min(ad[i],ad2[i])*-));
}
printf("%d\n",sum);
}
return ;
}
TLE的：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int n,a[],d[],w[],sum,len,l2;
int er(int q[],int l,int r,int key)//好好研究二分
{
int mid;
while(l<=r)
{
mid=(l+r)/;
if(q[mid]==key)
{
return mid;
}
else if(q[mid]>key)
{
r=mid-;
}
else l=mid+;
}
return l;
}
int er2(int q[],int l,int r,int key)//好好研究二分
{
int mid;
while(l<=r)
{
mid=(l+r)/;
if(q[mid]==key)
{
return mid;
}
else if(q[mid]>key)
{
l=mid+;
}
else r=mid-;
}
return l;
}
int main()
{
int we,wei;
while(scanf("%d",&n)!=EOF)
{
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
sum=;
len=;
d[len]=a[];
for(int i=; i<=n; i++)
{
if(a[i]>d[len])
{
d[++len]=a[i];
l2=;
w[l2]=a[i];
for(int j=i+; j<=n; j++)
{
if(a[j]<w[l2])
{
w[++l2]=a[j];
if(l2==len)
{
break;
}
}
else
{
wei=er2(w,,l2,a[j]);
w[wei]=a[j];
}
}
if(l2<=len) sum=max(sum,(*l2-));
//printf("sum==%d\n",sum);
}
else
{
we=er(d,,len,a[i]);
d[we]=a[i];
if(len<=) continue;
l2=;
w[l2]=a[i];
for(int j=i+; j<=n; j++)
{
if(a[j]<w[l2])
{
w[++l2]=a[j];
if(l2==we)
{
break;
}
}
else
{
wei=er2(w,,l2,a[j]);
w[wei]=a[j];
}
}
if(l2<=we) sum=max(sum,(*l2-));
//printf("sum==%d\n",sum);
}
}
printf("%d\n",sum);
}
return ;
}
最新文章
- Trie URAL 7192 Chip Factory (15长春J)
- python之信用卡ATM（第五天）
- npm 替换为 cnpm
- opencv单目摄像机标定（二）
- linux基础-附件1 linux系统启动流程
- iOS - UISlider
- [实变函数]2.2 聚点 (cluster point), 内点 (interior point), 界点 (boundary point)
- Java学习笔记——static关键字与静态的使用方法
- 【转载】跟我一起云计算（6）——openAPI
- 关于async和await的一些误区实例详解
- 自定义View的封装
- BZOJ 3685: 普通van Emde Boas树( 线段树 )
- C++基础知识－Day5
- Netty学习记录
- loj#2509. 「AHOI / HNOI2018」排列(思维题 set)
- ASP.NET MVC 4 (六) 帮助函数
- JAVA的环境变量配置（方式二）
- Flex + .Net从本地选择一个图片上传到服务器
- 突破MSDE 的2GB数据限制
- python 字典元素值的乘积