読者です 読者をやめる 読者になる 読者になる

AOJ 0191 Baby Tree

404 Not Found
やっとまともにDP解けたー!!!!!(嬉)

#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
	int n, m;
	while(scanf("%d %d\n", &n, &m), n || m){
		long double g[n][n];
		/* dp[a][b]は、a回目にbの肥料を与えた時のaまでの成長率の最大値 */
		long double dp[m][n];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				scanf("%Lf", &g[i][j]);
			}
		}
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				dp[i][j] = 0;
			}
		}
		for(int i = 0; i < n; i++) dp[0][i] = 1;
		
		for(int i = 1; i < m; i++){
			for(int j = 0; j < n; j++){
				for(int k = 0; k < n; k++){
					dp[i][j] = max(dp[i][j], dp[i - 1][k] * g[k][j]);
				}
			}
		}
		long double res = 0;
		for(int i = 0; i < n; i++){
			res = max(res, dp[m - 1][i]);
		}
		printf("%.2Lf\n", res);
	}
	
	return 0;
}