题目链接：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[10002],d[10002],w[10002],ad[10002],ad2[10002],sum,len,l2; int er(int q[],int l,int r,int key)//好好研究二分 { int mid; while(l<=r) { mid=(l+r)/2; if(q[mid]==key) { return mid; } else if(q[mid]>key) { r=mid-1; } else l=mid+1; } return l; } int main() { int we; while(scanf("%d",&n)!=EOF) { for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } sum=1; len=1; d[len]=a[1]; ad[1]=1; for(int i=2; i<=n; i++) { if(a[i]>d[len]) { d[++len]=a[i]; ad[i]=len; } else { we=er(d,1,len,a[i]); d[we]=a[i]; ad[i]=we; } } l2=1; w[l2]=a[n]; ad2[n]=1; for(int i=n-1; i>=1; i--) { if(a[i]>w[l2]) { w[++l2]=a[i]; ad2[i]=l2; } else { we=er(w,1,l2,a[i]); w[we]=a[i]; ad2[i]=we; } } for(int i=1;i<=n;i++) { sum=max(sum,(min(ad[i],ad2[i])*2-1)); } printf("%d ",sum); } return 0; }
TLE的：
#include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> #include <math.h> using namespace std; int n,a[10002],d[10002],w[10002],sum,len,l2; int er(int q[],int l,int r,int key)//好好研究二分 { int mid; while(l<=r) { mid=(l+r)/2; if(q[mid]==key) { return mid; } else if(q[mid]>key) { r=mid-1; } else l=mid+1; } return l; } int er2(int q[],int l,int r,int key)//好好研究二分 { int mid; while(l<=r) { mid=(l+r)/2; if(q[mid]==key) { return mid; } else if(q[mid]>key) { l=mid+1; } else r=mid-1; } return l; } int main() { int we,wei; while(scanf("%d",&n)!=EOF) { for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } sum=1; len=1; d[len]=a[1]; for(int i=2; i<=n; i++) { if(a[i]>d[len]) { d[++len]=a[i]; l2=1; w[l2]=a[i]; for(int j=i+1; j<=n; j++) { if(a[j]<w[l2]) { w[++l2]=a[j]; if(l2==len) { break; } } else { wei=er2(w,1,l2,a[j]); w[wei]=a[j]; } } if(l2<=len) sum=max(sum,(2*l2-1)); //printf("sum==%d ",sum); } else { we=er(d,1,len,a[i]); d[we]=a[i]; if(len<=1) continue; l2=1; w[l2]=a[i]; for(int j=i+1; j<=n; j++) { if(a[j]<w[l2]) { w[++l2]=a[j]; if(l2==we) { break; } } else { wei=er2(w,1,l2,a[j]); w[wei]=a[j]; } } if(l2<=we) sum=max(sum,(2*l2-1)); //printf("sum==%d ",sum); } } printf("%d ",sum); } return 0; }