题意
\(Wavio\) 是整数序列,有如下特点:
- 它的长度总为奇数,即 \(2n + 1\);
- 前 \(n+1\) 个数构成一个严格的上升序列,后 \(n+1\) 个数构成一个严格下降的序列;
- 任意相邻两个数不会相同
多组输入,给出 \(n\),接下来 \(n\) 个数,求此数列中 \(Wavio\) 序列的最大长度。
分析
对于每个数, 求出它前面有多少数比他小,后面有多少数比他大,
两者取小,再乘 \(2\) 减 \(1\),然后就可以得到以这个点为中心 \(Wavio\) 序列的长度;
从前往后求一次 LIS,再从后往前求一次;
因为 \(d_i\) 表示到下标为 \(i\) 的数时 LIS 的长度;在第二次求的时候可以直接取小
最后循环一遍答案就是 \(ans = max(ans, d_i \times 2-1)\);
用 \(n^2\) 的方法求 LIS 会超时,要用 \(n \times \log n\) 的方法求。
\(Code\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 10010;
const int INF = 0x3f3f3f3f;
int d[maxn], a[maxn], h[maxn];
int BFind(int c[], int len, int x)
{
int l = 0, r = len, mid;
while (l <= r) {
mid = (l+r)/2;
if (x < c[mid]) r -= 1;
else if (x > c[mid]) l += 1;
else return mid;
}
return l;
}
int main()
{
int n;
while (scanf ("%d", &n) != EOF) {
memset (h, 0, sizeof (h));
for (int i = 1; i <= n; i ++)
scanf ("%d", &a[i]);
int len = 1;
h[0] = -INF; h[1] = a[1];
for (int i = 1; i <= n; i ++) {
int x = BFind(h, len, a[i]);
h[x] = a[i];
len = max (len, x);
d[i] = len;
}
h[0] = -INF; h[1] = a[n]; len = 1;
for (int i = n; i >= 1; i --) {
int x = BFind(h, len, a[i]);
h[x] = a[i];
len = max (len, x);
d[i] = min(d[i], len);
}
int ans = 1;
for (int i = 1; i <= n; i++) {
ans = max (ans , d[i] * 2 - 1 );
}
printf ("%d\n", ans );
}
return 0;
}
原文地址:http://www.cnblogs.com/mrCrazyWolf/p/16928405.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性