题目链接：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 ;
}