Poj Solution 2127

http://poj.org/problem?id=2127

/* @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;
   }
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *