poj 2127 Greatest Common Increasing Subsequence （最长公共递增子序列） - c++编程基础

Greatest Common Increasing Subsequence

Time Limit: 10000MS		Memory Limit: 65536K
Total Submissions: 8888		Accepted: 2345
Case Time Limit: 2000MS		Special Judge

Description

You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length.
Sequence S₁ , S₂ , . . . , S_N of length N is called an increasing subsequence of a sequence A₁ , A₂ , . . . , A_M of length M if there exist 1 <= i₁ < i₂ < . . . < i_N <= M such that S_j = A_{i_j} for all 1 <= j <= N , and S_j < S_j+1 for all 1 <= j < N .

Input

Each sequence is described with M --- its length (1 <= M <= 500) and M integer numbers A_i (-2³¹ <= A_i < 2³¹ ) --- the sequence itself.

Output

On the first line of the output file print L --- the length of the greatest common increasing subsequence of both sequences. On the second line print the subsequence itself. If there are several possible answers, output any of them.

Sample Input

5
1 4 2 5 -12
4
-12 1 2 4

Sample Output

2
1 4

Source

Northeastern Europe 2003, Northern Subregion

题意：

给出两个序列a、b，求最长公共递增子序列。

思路：

dp[j]表示以b[j]结尾的LCIS的长度。

每次用a[i]去更新dp[j]，则

if(a[i]==b[j]) dp[j]=max(dp[j],dp[k]); (1<=k

维护好k的值，那么就可以将复杂度降到O(n*m)了。

由于要记录路径，用一维的dp、pre不太好处理，我用的是二维的，递归输出路径。

思路来源：推荐

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 1005 #define MAXN 100005 #define mod 100000000 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,k,ans,cnt,tot,flag; int ai,aj; int a[505],b[505]; int dp[505][505],px[505][505],py[505][505]; void output(int x,int y,int last) { if(x==0||y==0) return ; output(px[x][y],py[x][y],y); if(y!=last) { cnt++; if(cnt==1) printf("%d",b[y]); else printf(" %d",b[y]); } } void solve() { int i,j,k,t; memset(dp,0,sizeof(dp)); memset(px,0,sizeof(px)); memset(py,0,sizeof(py)); ans=0; for(i=1;i<=n;i++) { k=0; for(j=1;j<=m;j++) { dp[i][j]=dp[i-1][j]; px[i][j]=i-1,py[i][j]=j; if(b[j]==a[i]) { if(dp[i][j]
             
              ans) { ans=dp[i][j]; ai=i,aj=j; } } } printf("%d\n",ans); if(ans==0) return ; cnt=0; output(ai,aj,-1); printf("\n"); } int main() { int i,j,t; while(~scanf("%d",&n)) { for(i=1;i<=n;i++) { scanf("%d",&a[i]); } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d",&b[i]); } solve(); } return 0; } /* 7 1 2 4 0 1 4 5 6 0 3 1 2 4 5 */