首页 > 代码库 > HDURevenge of Segment Tree(第二长的递增子序列)
HDURevenge of Segment Tree(第二长的递增子序列)
HDURevenge of Segment Tree(第二长的递增子序列)
题目链接
题目大意:这题是求第二长的递增子序列。
解题思路:用n^2的算法来求LIS,但是这里还要记录一下最长的那个序列是否有多种组成方式,如果>= 2, 那么第二长的还是最长的LIS的长度,否则就是LIS - 1;
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int l[maxn], c[maxn];
int arr[maxn];
int main () {
int T, n;
scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%d", &arr[i]);
for (int i = 1; i <= n; i++)
l[i] = c[i] = 1;
int ans = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
if (l[j] + 1 > l[i]) {
l[i] = l[j] + 1;
c[i] = c[j];
} else if (l[j] + 1 == l[i])
c[i] = 2;//之前直接加上c[j],结果会int溢出,导致错误。
}
}
ans = max (ans, l[i]);
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (l[i] == ans)
cnt += c[i];
if (cnt > 1)
printf ("%d\n", ans);
else
printf ("%d\n", ans - 1);
}
return 0;
}
HDURevenge of Segment Tree(第二长的递增子序列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。