最长公共上升子序列(LCIS)ZOJ 2432

本文主要是介绍最长公共上升子序列(LCIS)ZOJ 2432，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

立方算法:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define M 505
using namespace std;
typedef long long LL;
LL a[M],b[M];
int dp[M][M];
int main()
{//freopen("in.txt","r",stdin);int T;cin>>T;while(T--){int n1,n2;cin>>n1;for(int i=1; i<=n1; i++)cin>>a[i];cin>>n2;for(int i=1; i<=n2; i++)cin>>b[i];memset(dp,0,sizeof(dp));for(int i=1; i<=n1; i++){for(int j=1; j<=n2; j++){dp[i][j]=dp[i-1][j];if(a[i]==b[j])dp[i][j]=1;if(a[i]==b[j])for(int k=1; k<j; k++){if(b[j]>b[k])dp[i][j]=max(dp[i][j],dp[i][k]+1);}}}int ans=0;for(int j=1;j<=n2;j++)if(dp[n1][j]>ans){ans=dp[n1][j];}cout<<ans<<endl;if(T)cout<<endl;}return 0;
}

平方算法:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define M 505
using namespace std;
typedef long long LL;
LL a[M],b[M];
int dp[M][M];
int main()
{//freopen("in.txt","r",stdin);int T;cin>>T;while(T--){int n1,n2;cin>>n1;for(int i=1; i<=n1; i++)cin>>a[i];cin>>n2;for(int i=1; i<=n2; i++)cin>>b[i];memset(dp,0,sizeof(dp));for(int i=1; i<=n1; i++){int max_=0;for(int j=1; j<=n2; j++){dp[i][j]=dp[i-1][j];if(a[i]>b[j]&&dp[i][j]>max_)max_=dp[i][j];else if(a[i]==b[j])dp[i][j]=max_+1;}}int ans=0;for(int i=1; i<=n2; i++)ans=max(ans,dp[n1][i]);cout<<ans<<endl;if(T)cout<<endl;}return 0;
}

这篇关于最长公共上升子序列(LCIS)ZOJ 2432的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---