AOJ

# # 解答

Naive recursive solution.

#define INTMAX (1 << 21)

#define MAX 100

Int mcm(Int p[], Int left, Int right) {

if (left == right) return 0;

Int min_ = INTMAX;
loop(sep,left,right) {
Int cost = mcm(p, left, sep) + mcm(p, sep+1, right);
cost += p[left - 1] * p[sep] * p[right];
if (cost < min_) min_ = cost;
}

return min_;
}

int main(void) {
Int n;
cin >> n;
Int p_len = n + 1;
Int p[p_len];
cin >> p[0] >> p[1];
loop(i, 2, p_len) {
cin >> p[i] >> p[i];
}
cout << mcm(p, 1, n) << endl;
return 0;
}


# # 解答

Bottom up dynamic programming. O(n^3)

#define INTMAX (1 << 21)

#define MAX 100

Int mcm(Int p[], Int n) {
Int mincosts[n][n];
loop(i,1,n) mincosts[i][i] = 0;

loop(chain,2,n) {
loop(l,1,n-chain+1) {
Int r = l + chain - 1;
mincosts[l][r] = INTMAX;
loop(k,l,r) {
Int cost = mincosts[l][k] + mincosts[k+1][r];
cost += p[l-1] * p[k] * p[r];
if (cost < mincosts[l][r]) mincosts[l][r] = cost;
}
}
}

return mincosts[1][n-1];
}

int main(void) {
Int n;
cin >> n;
Int p_len = n + 1;
Int p[p_len];
cin >> p[0] >> p[1];
loop(i, 2, p_len) {
cin >> p[i] >> p[i];
}
cout << mcm(p, p_len) << endl;
return 0;
}


リモートフリーランス。ウェブサービス、スマホアプリエンジニア。

お仕事のご依頼・お問い合わせはこちら