本文共 845 字，大约阅读时间需要 2 分钟。
题目大意：
Wavio Sequence是这样的一种数字序列：
它的长度为2*n+1, 前n+1个数字是严格递增的，后n+1个数字是严格递减的。
然后任意给一个序列，问它的Wavio Sequence子序列最长可以是多少？
分析：
对于第i个字符，如果我们知道0～i的最长递增序列， 并且知道i～n的最长递减序列，那么我们就可以知道以i为中心点的最长的Wavio Sequence。
所以, left_up[i]表示以i为结束点的最长递增序列长度， right_down[i]表示以i为起点的最长递减序列。
接下来就是求最长递增子序列了，用nlgn的复杂度求出这两个数组，然后枚举中点i就可以计算出答案了。
#include #include #include #include #include #include using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 10010;int n, arr[MAXN];int left_up[MAXN], right_down[MAXN];vector vt;int main(){ while(~scanf("%d", &n)){ for(int i=0; i =0; --i){ if(vt.empty() || vt.back() < arr[i]){ vt.push_back(arr[i]); }else{ int pt = lower_bound(vt.begin(), vt.end(), arr[i])-vt.begin(); vt[pt] = arr[i]; } right_down[i] = vt.size(); } int ans = 0; for(int i=0; i
转载地址：http://tvzni.baihongyu.com/