本文主要是介绍【UVA】10534 - Wavio Sequence（LIS最长上升子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题一看10000的数据量就知道必须用nlog(n)的时间复杂度。
所以特意去看了最长上升子序列的nlog(n)的算法。
如果有2个位置，该位置上的元素为A[i]和A[j],并且他们满足以下条件:
1.dp[i] = dp[j] (dp[x]代表以x结尾的最长上升子序列长度)
2.A[i] < A[j]
3.i < j
那么毫无疑问，选择dp[i] 一定优于选择dp[j]
那么我们可以利用g[i]表示长度为i的序列的最后一个元素的最小值.
每次拿到一个A[i],在g[i]里面寻找到一个元素，使得g[t] >= A[i].
dp[i] = t;
之后更新最小值 g[t] = A[i];
求最大下降子序列的话返回来遍历一遍就行了。
之后 ans = max(ans, min(dp[i],dp[j]) * 2 - 1);
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<ctime>
#include<cmath>
#include<string>
#include<iomanip>
#include<climits>
#include<cctype>
#include<deque>
#include<list>
#include<sstream>
#include<vector>
#include<cstdlib>
using namespace std;
#define _PI acos(-1.0)
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pill;
/*======================================
======================================*/
#define MAXD 10010
#define INF (1 << 30)
void LIS1(int dp[],int A[],int n){int g[MAXD];for(int i = 1 ; i <= n ; i++) g[i] = INF;for(int i = 1 ; i <= n ; i++){int k = lower_bound(g + 1 , g + n + 1 , A[i]) - g;dp[i] = k;g[k] = A[i];}return ;
}
void LIS2(int dp[],int A[],int n){int g[MAXD];for(int i = 1 ; i <= n ; i++) g[i] = INF;for(int i = n ; i >= 1 ; i--){int k = lower_bound(g + 1 , g + n + 1 , A[i]) - g;dp[i] = k;g[k] = A[i];}return ;
}
int main(){int n;int A[MAXD];while(scanf("%d",&n) != EOF){for(int i = 1 ; i <= n ; i++)scanf("%d",&A[i]);int dp1[MAXD] , dp2[MAXD];LIS1(dp1,A,n);LIS2(dp2,A,n);int ans = 0 ;for(int i = 1 ; i <= n ; i++){int t = min(dp1[i],dp2[i]);ans = max(ans,2 * t - 1);}printf("%d\n",ans);}return 0;
}
这篇关于【UVA】10534 - Wavio Sequence（LIS最长上升子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
