2013
11-10

# 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;
}
}

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;