1080.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

import java.util.*;

public class Main {
	
	static int get( char c ) {
		if( c == 'A' )
			return 0;
		else if( c == 'C' )
			return 1;
		else if( c == 'G' )
			return 2;
		else
			return 3;
	}
	
	static int [][]p = new int[][]{
		{ 5,  -1, -2, -1 },
		{ -1,  5, -3, -2 },
		{ -2, -3,  5, -2 },
		{ -1, -2, -2,  5 }
	};
	
	static int d[] = new int[]{ -3, -4, -2, -1 };
	static int [][] ans = new int[110][110];
	static char [] a, b;
	static public void main( String [] string ) throws Exception{
		Scanner cin = new Scanner( System.in );
		int n = cin.nextInt();
		
		while( (n--) > 0 ) {
			cin.nextInt();
			a = cin.next().toCharArray();
			cin.nextInt();
			b = cin.next().toCharArray();
			
			ans[a.length][b.length] = 0;
			
			for( int i=a.length; i>=0; i-- )
			for( int j=b.length; j>=0; j-- ) 
			if( i != a.length || j != b.length ){
				ans[i][j] = -10000000;
				if( i != a.length )
					ans[i][j] = Math.max( ans[i][j], 
							ans[i+1][j]+d[get(a[i])] );
				if( j != b.length )
					ans[i][j] = Math.max( ans[i][j], 
							ans[i][j+1]+d[get(b[j])] );
				if( i != a.length && j != b.length )
					ans[i][j] = Math.max( ans[i][j], 
							ans[i+1][j+1]+p[get(a[i])][get(b[j])] );
			}
			System.out.println( ans[0][0] );
		}
	}
}