首页 > 专题系列 > Java解POJ > POJ 2127 Greatest Common Increasing Subsequence [解题报告] Java
2013
11-10

POJ 2127 Greatest Common Increasing Subsequence [解题报告] Java

Greatest Common Increasing Subsequence

问题描述 :

You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length.

Sequence S1 , S2 , . . . , SN of length N is called an increasing subsequence of a sequence A1 , A2 , . . . , AM of length M if there exist 1 <= i1 < i2 < . . . < iN <= M such that Sj = Aij for all 1 <= j <= N , and Sj < Sj+1 for all 1 <= j < N .

输入:

Each sequence is described with M — its length (1 <= M <= 500) and M integer numbers Ai (-231 <= Ai < 231 ) — the sequence itself.

输出:

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.

样例输入:

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

样例输出:

2
1 4

解题代码:

/* @author: */
import java.util.*;
public class Main {
  static int ans[][], xf[][], yf[][];
  static int as[][], len[];
  static public void main( String [] str ) throws Exception{
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt(), m;
    int [] a, b;
    a = new int[n];
    for( int i=0; i< n; i++ )
	a[i] = cin.nextInt();
    m = cin.nextInt();
    b = new int[m];
    for( int i=0; i< m; i++ )
	b[i] = cin.nextInt();
		
    ans = new int[n][m];
    xf = new int[n][m];
    yf = new int[n][m];
    as = new int[n][m];
    len = new int[n];
			
    for( int i=0; i< n; i++ ) {
	for( int j=0; j< m; j++ )
	  if( a[i] == b[j] )
	     as[i][len[i]++] = j;
			
       int [] t = new int[len[i]];
       System.arraycopy( as[i], 0, t, 0, len[i] );
       as[i] = t;
    }
			
    int bx = -1, by = -1;
    for( int i=n-1; i>=0; i-- )
	for( int j=m-1; j>=0; j-- ) 
	  if( a[i] == b[j] ){
	    int t, best = 0;
	    xf[i][j] = yf[i][j] = -1;
           for( int k=i+1; k< n; k++ ) 
	      if( a[k] > a[i]) {
		 t = Arrays.binarySearch( as[k], j+1 );
		 if( t < 0 )
		   t = -t-1;
		 if( t != as[k].length ) {
		   t = as[k][t];
		   if( ans[k][t] > best ) {
		     best = ans[k][t];
		     xf[i][j] = k;
		     yf[i][j] = t;
		    }
		  }
	      }
	   ans[i][j] = best+1;
	   if( bx < 0 || ans[i][j] > ans[bx][by] ) {
		bx = i;
		by = j;
	   }
	 }
		
	if( bx < 0 )
	  System.out.println( 0 + "\n" );
	else {
	  System.out.println( ans[bx][by] );
	while( bx != -1 ) {
	  System.out.print( a[bx] );
	  int x = xf[bx][by], y = yf[bx][by];
	  bx = x;
	  by = y;
	  if( bx != -1 )
	    System.out.print( " " );
	}
	System.out.println();
    }
    return;
   }
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;