http://lx.lanqiao.cn/problem.page?gpid=T417
题意：……
思路：n=1000，一开始觉得区间DP会超时，后来想不到其他做法就这样做了，居然没超时。
状态转移：dp[l][r] = min(dp[l][r], dp[l][k] * dp[k][r] + num[l]*num[k]*num[r]).
表示用l*k的矩阵去和k*r的矩阵相乘，然后取最小。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 100000000000000000LL;
LL num[];
LL dp[][];
int main() {
LL ans = ;
int n; cin >> n;
for(int i = ; i <= n; i++) scanf("%lld", &num[i]), dp[i][i] = num[i];
for(int len = ; len <= n; len++) {
for(int l = ; l + len <= n; l++) {
int r = l + len;
dp[l][r] = INF;
for(int k = l + ; k < r; k++) {
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + num[l] * num[k] * num[r]);
}
}
}
cout << dp[][n] << endl;
return ;
}