首页 > 代码库 > POJ 2127 LCIS DP
POJ 2127 LCIS DP
http://poj.org/problem?id=2127
#include <iostream> #include <algorithm> #include <cstring> #include <queue> #include <cstdio> #include <map> #include <vector> using namespace std; const int N=5e2+20; const int inf=2e8; //题意:a,b两个数组,长度<=500,a[i],b[i]<=1e9,求出a,b最长公共递增子序列? //设dp[i][j] a的前i个字符和b的前j个字符&&以b[j]结尾的LCIS长度 //a[i]!=b[j]: dp[i][j]=dp[i-1][j] //a[i]==b[j]: dp[i][j]=max(dp[i-1][k]+1 ) ( 1<=k<j,b[k]<b[j]=a[i]) int dp[N][N];//a的前i个字符和b的前j个字符&&以b[j]结尾的LCIS长度 int path[N][N];//LCIS 以b[j]结尾,记录此时决策 int n,m,a[N],b[N]; vector<int> res; int main() { while(cin>>n) { res.clear(); int p,q; for(int i=1;i<=n;i++) cin>>a[i]; cin>>m; for(int i=1;i<=m;i++) cin>>b[i]; memset(dp,0,sizeof(dp)); memset(path,0,sizeof(path)); int ans=0,mj; for(int i=1;i<=n;i++) { int mx=0; for(int j=1;j<=m;j++) { dp[i][j]=dp[i-1][j];//a[i]!=b[j] path[i][j]=-1; if(b[j]<a[i]&&dp[i-1][j]>mx) { mx=dp[i-1][j]; mj=j; } else if(a[i]==b[j]) { dp[i][j]=mx+1; path[i][j]=mj; } if(ans<dp[i][j]) { ans=dp[i][j]; p=i,q=j; } } } cout<<ans<<endl; while(ans) { if(path[p][q]>-1) { ans--; res.push_back(b[q]); q=path[p][q]; } p--; } for(int i=res.size()-1;i>=0;i--) printf("%d%c",res[i],i==0?‘\n‘:‘ ‘); } return 0; }
POJ 2127 LCIS DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。