发布时间: 2017年7月9日 18:17 最后更新: 2017年7月9日 21:05 时间限制: 1000ms 内存限制: 128M
描述如果一个序列有奇数个正整数组成，不妨令此序列为 a1,a2,a3,...,a2∗k+1 ( 0<=k )，并且 a1,a2...ak+1 是一个严格递增的序列， ak+1,ak+2,...,a2∗k+1 ,是一个严格递减的序列，则称此序列是A序列。
比如1 2 5 4 3就是一个A序列。
现在Jazz有一个长度为 n 的数组，他希望让你求出这个数组所有满足A序列定义的子序列里面最大的那个长度。（子序列可以不连续）
比如1 2 5 4 3 6 7 8 9，最长的A序列子串是1 2 5 4 3。
输入多组输入，每组两行。 第一行是 n ，表示给的数组的长度。 第二行有 n 个数(int范围)，即给你的数组。 1<=n<=500000 。
输出每组输入输出一行，即最长的A序列子串的长度。
样例输入1 9 1 2 5 4 3 6 7 8 9 样例输出15
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 5e6 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n; int a[N], b[N], c[N], d[N], f[N]; int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } //算前 int len = 0; for (int i = 1; i <= n; ++i) { if (a[i] > d[len])d[++len] = a[i], f[i] = len; else { int l = 1; int r = len; while (l < r) { int mid = (l + r) >> 1; if (a[i] <= d[mid])r = mid; else l = mid + 1; } d[l] = a[i]; f[i] = l; } } memcpy(b, f, sizeof(b)); //算后 reverse(a + 1, a + n + 1); len = 0; for (int i = 1; i <= n; ++i) { if (a[i] > d[len])d[++len] = a[i], f[i] = len; else { int l = 1; int r = len; while (l < r) { int mid = (l + r) >> 1; if (a[i] <= d[mid])r = mid; else l = mid + 1; } d[l] = a[i]; f[i] = l; } } memcpy(c, f, sizeof(c)); reverse(c + 1, c + n + 1); //统计 int ans = 1; for(int i = 1; i <= n; ++i) { int len = min(b[i], c[i]); gmax(ans, len * 2 - 1); } printf("%d\n", ans); } return 0; } /* 【分析】 LIS模板题 */