#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
using namespace std;

typedef long long int64;
const int oo = 0x3f3f3f3f;
const int NUM = 105;
int cards[NUM], dp[NUM][NUM];

//dp [i][j] = min (dp [i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j])
//最后一个取第k个数

int main() {
    int n;
    cin >> n;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = 0;
        dp[i][i + 1] = 0;
    }
    for (int i = 1; i <= n; ++i) cin >> cards[i];
    for (int i = n; i >= 1; --i) {
        for (int j = i; j <= n; ++j) {
            for (int k = i; k <= j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cards[i] * cards[k] * cards[j]);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}
//上面那个程序，poj上果断ac!
//zoj上wa!scu也是。

• Re:小心！这个数据弱！这里ac!zoj上wa! (48) Alextokc 2017-04-13 18:27:36