AOJ0191 Baby Tree

解法
直前与えた肥料が何であるかが、今回に何を与えるのが最適であるかを決める。
よって、状態として「肥料を与えた回数」と「直前に与えた肥料」を持ち、成長率を最大化するDPをすればよい。
具体的には、k 日目に肥料 j を与えたときの成長率は、k-1 日目に肥料 i を与えていたとして、その上で 肥料 j を与えたという情報で更新出来る。よって３重ループで解ける。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main() {
  
  int N, M;
  
  while(cin >> N >> M && (N|M)) {
    vector<vector<double> > p(N, vector<double>(N, 0));
      
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) cin >> p[i][j];
      
    vector<vector<double> > dp(M, vector<double>(N, 0));
    for(int i=0; i<N; i++) dp[0][i] = 1.0;
	
    for(int k=1; k<M; k++)
      for(int i=0; i<N; i++)
	for(int j=0; j<N; j++)
	  dp[k][j] = max(dp[k][j], dp[k-1][i]*p[i][j]);
    
    double res = 0.0;
    for(int i=0; i<N; i++) res = max(res, dp[M-1][i]);
    
    printf("%.2f\n", res);
  }  
  
  return 0;
}