AOJ 0191 - Baby Tree + 戯言

四捨五入がだめだったっぽい．ただprintf("%.2f", hoge)でいい．*1
DPが少しずつできるようになってきた．全探索を思い浮かべるといいかんじ．
はじめに肥料を肥料0として，次に肥料nをあげたときの倍率を1とすると，処理がちょっとだけ楽になるよー．
10^6回は超えないので，最初に選ぶ肥料をiとしてループ回してもいいっぽい．

#include<iostream>
#include<cstdio>

const double EPS = 1e-10;
int n, m;
//memo[i][j]: 直前にjを入れてi回目のときの最大倍率
//a[i][j]: 直前i
double a[101][101], memo[101][101];

double rec(int i, int j){
	if(memo[i][j] > -EPS){
		return memo[i][j];
	}

	if(i == m){
		return 1;
	}

	double res = 0;
	for(int u=1;u<=n;u++){
		res = std::max(res, a[j][u] * rec(i+1, u));
	}

	return memo[i][j] = res;
}

int main(){
	while(std::cin >> n >> m, n){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				std::cin >> a[i][j];
			}
		}

		for(int i=1;i<101;i++){
			a[0][i] = 1;
		}

		for(int i=0;i<101;i++){
			for(int j=0;j<101;j++){
				memo[i][j] = -1;
			}
		}
		
		printf("%.2f\n", rec(0, 0));
	}
}

余談: 岩手県(局所的)では新成人にKoboが配られるそうですね．
もし宮守女子に配られたらとかおもしろそうですね．
電波入らない姉帯さんとか「だるい」とか言って投げておく白望さんとかとか

*1:printfすごい