首页 > 代码库 > 最长上升子序列（模板）
最长上升子序列（模板）
最长上升子序列（O^n^2）算法
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <iomanip> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define INF 0x3f3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int a[100006],dp[100006],n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); int maxn=-1; for(int i=1;i<=n;i++) { dp[i]=1; for(int j=1;j<=i;j++) { if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); } maxn=max(maxn,dp[i]); } printf("%d\n",maxn); return 0; }
(Onlogn)算法
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <iomanip> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define INF 0x3f3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int x,dp[100006],n; int main() { scanf("%d",&n); int top=0; dp[0]=-1; for(int i=0;i<) for(int i=0;i<n;i++) { scanf("%d",&x); if(x>dp[top]) dp[++top]=x; else//替换更新 { int l=1,r=top; while(l<=r) { int mid=(l+r)>>1; if(x>dp[mid]) l=mid+1; else r=mid-1; } dp[l]=x; } } }
模板题 http://poj.org/problem?id=2533
最长上升子序列（模板）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。