首页 > 代码库 > UVa 10534 波浪子序列（快速求LIS）
UVa 10534 波浪子序列（快速求LIS）
https://vjudge.net/problem/UVA-10534
题意：
给定一个长度为n的整数序列，求一个最长子序列（不一定连续），使得该序列的长度为2k+1，前k+1个数严格递增，后k+1个数严格递减。
思路：
先正着求一遍LIS，再反着求一遍LIS。
当然求法是得采用O（nlogn）的求法，这个网上有很多解释，我就不多介绍了。
最后的话枚举一遍就可以了，详见代码。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 using namespace std;12 typedef long long LL;13 typedef pair<int,int> pll;14 const int INF=0x3f3f3f3f;15 const int maxn=10000+5;16 17 int n;18 int a[maxn],r_a[maxn],g[maxn],d1[maxn],d2[maxn];19 20 int main()21 {22 //freopen("D:\\input.txt","r",stdin);23 while(~scanf("%d",&n))24 {25 for(int i=0;i<n;i++)26 {27 scanf("%d",&a[i]);28 r_a[n-i-1]=a[i];29 }30 31 int ans1=0;32 for(int i=1;i<=n;i++) g[i]=INF;33 for(int i=0;i<n;i++)34 {35 int k=lower_bound(g+1,g+n+1,a[i])-g;36 d1[i]=k; //记录了前i个数的最长子序列37 g[k]=a[i];38 ans1=max(ans1,d1[i]);39 }40 41 int ans2=0;42 for(int i=1;i<=n;i++) g[i]=INF;43 for(int i=0;i<n;i++)44 {45 int k=lower_bound(g+1,g+n+1,r_a[i])-g;46 d2[i]=k;47 g[k]=r_a[i];48 ans2=max(ans2,d2[i]);49 }50 51 //枚举递增和递减的分隔点52 int ans=0;53 for(int i=0;i<n;i++)54 {55 int temp=min(d1[i],d2[n-i-1]);56 temp=2*(temp-1)+1;57 if(ans<temp) ans=temp;58 }59 printf("%d\n",ans);60 }61 return 0;62 }
UVa 10534 波浪子序列（快速求LIS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。