次长上升子序列
题目描述
最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.
对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}
其中, 1<=x1<x2<x3…<xm<=n
本题的上升子序列应满足a[x1]<=a[x2]<=a[x3]…<=a[xm], 也就是说, 我们考虑的是非严格的上升子序列(或者说,不下降子序列)
两个子序列不同, 当且仅当有一个下标被一个子序列包含却不被另一个子序列包含.
给出一个数列, 你需要找出所有非严格的上升子序列中第二长的子序列的长度. 它有可能比最长上升子序列短, 也有可能和最长上升子序列一样长.
输入
每个输入包含多组测试数据,第一行一个整数T表示测试数据的组数.
接下来每组数据第一行一个整数n, 表示数列的长度,第二行n个整数表示数列.
输出
T行, 第i行一个数字表示第i组输入的次长上升子序列长度
样例输入 Copy
5
10
10 1 8 10 2 6 4 1 5 4
10
8 2 6 1 6 8 10 3 7 4
10
1 8 7 9 9 6 10 3 2 2
10
5 4 8 2 2 2 2 9 3 3
10
8 4 9 7 6 9 10 3 7 3
样例输出 Copy
4
4
5
5
4
提示
100%的数据, T=5, 1<=ai<=100000，n≤100000问题 A: 次长上升子序列
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.
对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}
其中, 1<=x1<x2<x3…<xm<=n
本题的上升子序列应满足a[x1]<=a[x2]<=a[x3]…<=a[xm], 也就是说, 我们考虑的是非严格的上升子序列(或者说,不下降子序列)
两个子序列不同, 当且仅当有一个下标被一个子序列包含却不被另一个子序列包含.
给出一个数列, 你需要找出所有非严格的上升子序列中第二长的子序列的长度. 它有可能比最长上升子序列短, 也有可能和最长上升子序列一样长.
输入
每个输入包含多组测试数据,第一行一个整数T表示测试数据的组数.
接下来每组数据第一行一个整数n, 表示数列的长度,第二行n个整数表示数列.
输出
T行, 第i行一个数字表示第i组输入的次长上升子序列长度
样例输入 Copy
5
10
10 1 8 10 2 6 4 1 5 4
10
8 2 6 1 6 8 10 3 7 4
10
1 8 7 9 9 6 10 3 2 2
10
5 4 8 2 2 2 2 9 3 3
10
8 4 9 7 6 9 10 3 7 3
样例输出 Copy
4
4
5
5
4
提示
100%的数据, T=5, 1<=ai<=100000，n≤100000问题 A: 次长上升子序列
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.
对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}
其中, 1<=x1<x2<x3…<xm<=n
本题的上升子序列应满足a[x1]<=a[x2]<=a[x3]…<=a[xm], 也就是说, 我们考虑的是非严格的上升子序列(或者说,不下降子序列)
两个子序列不同, 当且仅当有一个下标被一个子序列包含却不被另一个子序列包含.
给出一个数列, 你需要找出所有非严格的上升子序列中第二长的子序列的长度. 它有可能比最长上升子序列短, 也有可能和最长上升子序列一样长.
输入
每个输入包含多组测试数据,第一行一个整数T表示测试数据的组数.
接下来每组数据第一行一个整数n, 表示数列的长度,第二行n个整数表示数列.
输出
T行, 第i行一个数字表示第i组输入的次长上升子序列长度
样例输入
5
10
10 1 8 10 2 6 4 1 5 4
10
8 2 6 1 6 8 10 3 7 4
10
1 8 7 9 9 6 10 3 2 2
10
5 4 8 2 2 2 2 9 3 3
10
8 4 9 7 6 9 10 3 7 3
样例输出
4
4
5
5
4
提示
100%的数据, T=5, 1<=ai<=100000，n≤100000
因为要找第二长的子序列， 所以先贪心dp一下最长的非严格上升子序列， 然后我们再求一下得出这个序列的方案数， 如果得出最长的子序列方案数大于1，那么答案就是最长的方案书序列长度， 不然的会就是最长长度减1
#pragma GCC optimize(3 , "Ofast" , "inline")
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 10 ;
int dp[N] , a[N] , p[N] , now[N] ;
int main()
{
int n ;
int T ;
cin >> T ;
while(T --)
{
scanf("%d" , &n) ;
for(int i = 1; i <= n ;i ++) scanf("%d" , &a[i]) ;
memset(dp , 0 , sizeof dp) , memset(now , 0 , sizeof now) ;
memset(p , 0 , sizeof p) ;
int cnt = 0 ;
dp[++ cnt] = a[1] , p[1] = 1 ;
for(int i = 2 ; i <= n ;i ++)
{
if(a[i] >= dp[cnt]) dp[++ cnt] = a[i] , p[i] = cnt ;
else
{
int pos = upper_bound(dp + 1 , dp + cnt + 1 , a[i]) - dp ;
if(a[i] >= dp[pos - 1]) p[i] = pos ;
else p[i] = 1 ;
dp[pos] = a[i] ;
}
}
vector<int> v[N] ;
int ans = 0 ;
for(int i = 1; i <= n ;i ++)
{
if(p[i] == 1) now[i] ++ ;
for(auto x : v[p[i] - 1])
if(a[i] >= a[x]) now[i] += now[x] ;
if(p[i] == cnt) ans += now[i] ;
if(ans > 1) break ;
v[p[i]].push_back(i) ;
}
printf("%d\n" , cnt - (ans <= 1)) ;
}
}
