AOJ Problem 0191 : Baby Tree

404 Not Found

ベイビーツリーはかわいい。動的計画法全く出来なかったので練習に。

昔一瞬取り組んで検討もつかなかった記憶があるけど、問題文をよく読んで因果関係とか考えるとなんか分かる気がした!ということでsolve。

直前に何使ったか情報しか要らないわけだから、DP[m(何回目か)][n(その時何使ったか)]で動的計画法する。ちなみに[m]の部分は何回目かについて偶奇だけに着目することによって[2]の配列にしている。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)


int main(){
	int n, m ;
	while(cin >> n >> m , n){
		long double table[100][100];
		long double dp[2][100] = {{0.0}};

		rep(i,n)rep(j,n)cin >> table[i][j];
		rep(i,n)dp[0][i] = 1.0;
		bool sw = false;
		
		rep(i,m-1){ // kaisu 
			rep(j,n){ // chokuzen 
				rep(k,n){ // current
					dp[sw^1][k] = max(dp[sw^1][k] , dp[sw][j] * table[j][k]);
				}
			}
			sw ^= 1;
		}
		long double ret = 0;
		rep(i,n) ret = max(ret,dp[sw][i]);
		printf("%.2Lf\n",ret);
	}
}