AOJ 0191 Baby Tree

方針

メモ化再帰.
memo[i][j] := j番目の肥料を直前に与え，i回目の肥料を与える時の成長度の最大値

ソースコード

double g[128][128];
double memo[128][128];

int n, m;

double dfs(int c, int prev)
{
    if(c == m)
        return 1.0;
    if(memo[c][prev] != -1)
        return memo[c][prev];

    double res = -1;

    for(int i = 0; i < n; i++)
        res = max(res, dfs(c + 1, i) * (c == 0 ? 1.0 : g[prev][i]));
        
    return memo[c][prev] = res;
}

int main()
{
    double ans;

    while(cin >> n >> m, n|m)
    {
        fill((double *)memo, (double *)(memo + sizeof memo / sizeof *memo), -1);

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin >> g[i][j];

        printf("%.2lf\n", dfs(0, 0));
    }
}