functionrunfun.java

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

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


/**
 * ID:1579
 * 动态规划
 * @author yhm
 *
 */
public class FunctionRunFun {
	
	static int[][][] result = new int[21][21][21];

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		init();
		while(true){
			int[] array = new int[3];
			int num = 0;
			for(int i=0;i<3;i++){
				array[i] = cin.nextInt();
				if(array[i]==-1){
					num++;
				}				
			}
			if(num==3) break;
			int r = solve(array);
			String str = "w(";	
			for(int i=0;i<2;i++){
				str = str+array[i]+", "	;		
			}
			str+=array[2];
			str+=") = ";
			str+=r;
			System.out.println(str);
		}

	}
	static void init(){
		for(int i=0;i<=20;i++){
			for(int j=0;j<=20;j++){
				result[0][i][j] = 1;
				result[i][0][j] = 1;
				result[i][j][0] = 1;
			}
		}
		for(int a=1;a<=20;a++){
			for(int b=1;b<=20;b++){
				for(int c=1;c<=20;c++){

					if(a < b && b < c){
						result[a][b][c] = result[a][b][c-1] + result[a][b-1][c-1] - result[a][b-1][c]; 
					}
					else{
						result[a][b][c] = result[a-1][b][c] + result[a-1][b-1][c] + result[a-1][b][c-1] - result[a-1][b-1][c-1]; 
					}
																	
				}
			}
		}
	}
	static int solve(int[] array){
		if(array[0]<=0||array[1]<=0||array[2]<=0){
			return 1;
		}
		else if(array[0]>20||array[1]>20||array[2]>20){
			return result[20][20][20];
		}
		else{
			return result[array[0]][array[1]][array[2]];
		}
	}

}