ベイビーツリーはかわいい。動的計画法全く出来なかったので練習に。
昔一瞬取り組んで検討もつかなかった記憶があるけど、問題文をよく読んで因果関係とか考えるとなんか分かる気がした!ということで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); } }