humangenefunctions.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.Scanner;


/**
 * ID:1080
 * 动态规划
 * 注意求AGT到GTT，即求AG到GT加T与T，AGT到GT(AGT,-GT)加-与T，AG到GTT（-AG，GTT）加T与-
 * 三者的最大值。
 * 
 * @author yhm
 *
 */
public class HumanGeneFunctions {

	static int[][] a = new int[5][5];
	public static void main(String[] args) {
		for(int i=0;i<4;i++)
			a[i][i]=5;
		a[0][1]=a[1][0]=-1;a[0][2]=a[2][0]=-2;a[0][3]=a[3][0]=-1;a[0][4]=a[4][0]=-3;
		a[1][2]=a[2][1]=-3;a[1][3]=a[3][1]=-2;a[1][4]=a[4][1]=-4;
		a[2][3]=a[3][2]=-2;a[2][4]=a[4][2]=-2;
		a[3][4]=a[4][3]=-1;
		a[4][4]=0;
		
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=0;i<caseNum;i++){
			cin.nextInt();
			String str1 = cin.next();
			cin.nextInt();
			String str2 = cin.next();
			int r = solve(str1,str2);
			System.out.println(r);
		}
		
		
	}
	
	static int solve(String str1, String str2){
		int l1 = str1.length();
		int l2 = str2.length();
		int[][] cost = new int[l1+1][l2+1];
		int i=0,j=0;
		cost[0][0] = 0;
		for(i=1;i<=l1;i++){
			cost[i][0] = cost[i-1][0]+getValue(str1.charAt(i-1),'-');

		}
		for(j=1;j<=l2;j++){
			cost[0][j] = cost[0][j-1]+getValue('-',str2.charAt(j-1));
		}
		
		for(i=1;i<=l1;i++){
			for(j=1;j<=l2;j++){
				int temp1,temp2,temp3;
				temp1 = cost[i][j-1]+getValue('-',str2.charAt(j-1));
				temp2 = cost[i-1][j]+getValue(str1.charAt(i-1),'-');
				temp3 = cost[i-1][j-1]+getValue(str1.charAt(i-1),str2.charAt(j-1));
				int max = Math.max(temp1, temp2);
				max = Math.max(temp3, max);
				cost[i][j] = max;
			}
		}
		return cost[l1][l2];
	}
	
	static int getValue(char ch1,char ch2){
		int i = get(ch1);
		int j = get(ch2);
		return a[i][j];
	}
	
	static int get(char ch){
		if(ch=='A')return 0;
		else if(ch=='C')return 1;
		else if(ch=='G')return 2;
		else if(ch=='T')return 3;
		else return 4;
	}

}