decadence

個人のメモ帳

AOJ 0191 Baby Tree

動的計画法の勉強
AOJ 0191 404 Not Found

  • result[肥料を与えた回数][最後に与えた肥料]の最大値
  • 最後に値に影響して次の初期値が定まる、まさに動的計画法が使える問題である

何か色々無駄が多い気がするがこんなもんじゃないだろうか

import java.io.*;

class Sample{
	private static float[][] grow;
	public static void main(String[] args)throws FileNotFoundException,IOException{
		BufferedReader br = new BufferedReader(new FileReader("text.txt"));
		while(true){
			String input[] = br.readLine().split(" ");
			int in[] = new int[2];
			in[0] = Integer.parseInt(input[0]);
			in[1] = Integer.parseInt(input[1]);
			if(in[0] == 0) break;
			
			grow = new float[in[0]][in[0]];
			for(int i = 0; i < in[0]; ++i){
				String data[] = br.readLine().split(" ");
				for(int j = 0; j < data.length; ++j){
					grow[i][j] = Float.parseFloat(data[j]);
				}
			}
			float result = makeGrow(in[1]);
			System.out.println(result);
		}
	}
	private static float makeGrow(int count) {
		int kinds = grow.length;
		float result[][] = new float[count][kinds];
		float maxGrow = 0;
		if(count == 1) return 1.0F;
		for(int i = 0; i < kinds ; ++i){
			result[0][i] = 1;
		}
		for(int i = 1 ; i < count ; ++i){
			for(int j = 0; j < kinds; ++j){
				float max = 0;
				for(int k = 0; k < kinds; ++k){
					max = Math.max(max, result[i-1][k]*grow[j][k]);
				}
				result[i][j] = max;
			}
		}
		for(int i = 1; i < kinds; ++i){
			maxGrow = Math.max(maxGrow, result[count-1][i]);
		}
		return maxGrow;
	}
}
  • 追記

これ書いた時はAOJ登録もしてなかったし入力方法も出力方法も違うんでそのまま使ったりは出来ません