連鎖行列積を動的計画法で解く

連鎖行列積の問題を解きました。
両端の距離が小さい部分問題から解がうまっていくタイプのDPの典型問題です。

問題

Optimal Array Multiplication Sequence

ソースコード

const long long INF = 1LL<<60;
int n;
int r[16], c[16];
int mid[16][16];
long long dp[16][16];

inline string toString(int x) {
    ostringstream os;
    os << "A" << x;
    return os.str();
}

string printResult(int left, int right) {
    if (right - left == 0)
        return toString(left+1);
    return "(" + printResult(left, mid[left][right]) + " x " + printResult(mid[left][right]+1, right) + ")";
}

void solve(int &t) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = INF;
    
    for (int i = 0; i < n; i++)
        dp[i][i] = 0;
    
    for (int k = 1; k < n; k++) {
        for (int i = 0; i + k < n; i++) {
            int j = i + k;
            for (int m = i; m < j; m++) {
                long long tmp = dp[i][m] + dp[m+1][j] + r[i] * c[j] * c[m];
                if (dp[i][j] > tmp) {
                    dp[i][j] = tmp;
                    mid[i][j] = m;
                }
            }
        }
    }
    
    cout << "Case " << ++t << ": " << printResult(0, n-1) << endl;
}

int main() {
    int t = 0;
    while (scanf("%d", &n) == 1) {
        if (n == 0)
            break;
        
        for (int i = 0; i < n; i++)
            scanf("%d %d", r+i, c+i);
        
        solve(t);
    }
    
    return 0;
}