AOJ0191 Baby Tree

解法

---

自明なDP。
1回目に与えた肥料だけでは、苗木の大きさが変わりません。
2回目以降は、その回に与えた肥料と、その直前に与えた肥料との組み合わせによって苗木に 影響を与えます。良い影響を与えると苗木が伸び、悪い影響を与えると苗木が縮んでしまうこともあります。
ここからすべてを察した。

ソース

---

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
double dp[100][100],g[100][100];
int main(){
  int n, m;
  while(cin >> n >> m , n){
    for(int i = 0 ; i < n ; i++ )
      for(int j = 0 ; j < n ; j++ ) cin >> g[i][j];
    fill_n( dp[0], n, 1.0);
    fill_n( dp[1], 9900, 0.0);
    for(int i = 1 ; i < m ; i++ ) //回
      for(int prev = 0 ; prev < n ; prev++ ) // prev
        for(int now = 0 ; now < n ; now++ ) // now
          dp[i][now] = max( dp[i][now], dp[i - 1][prev] * g[prev][now]);
 
    cout << fixed << setprecision(2) << *max_element( dp[m - 1], dp[m - 1] + n ) << endl;
  }
}