每次删除一个数，代价是左右两边相邻的数的当前数的积
第一个和最后一个数不能删除
问最后只剩下第一个数的最后一个数的最小代价
思路
很简单的DP
正着考虑没有办法确定两边的数
那么就把每个区间内最后一次删除的数枚举出来，就可以确定左右两边的点是什么了
感觉挺对的
(dp_{i,j})表示还有区间([i,j])全部删完的最小代价，枚举一下最后删除的数然后直接统计贡献就可以了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1e2 + 10;
ll dp[N][N];
int n, a[N];
int main() {
#ifdef dream_maker
freopen("input.txt", "r", stdin);
#endif
memset(dp, 0x3f, sizeof(dp));
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 2; i < n; i++) dp[i][i] = a[i - 1] * a[i] * a[i + 1];
for (int len = 2; len <= n - 2; len++) {
for (int l = 2, r; (r = l + len - 1) < n; l++) {
dp[l][r] = min(dp[l][r], a[l] * a[l - 1] * a[r + 1] + dp[l + 1][r]);
dp[l][r] = min(dp[l][r], a[r] * a[l - 1] * a[r + 1] + dp[l][r - 1]);
for (int k = l + 1; k < r; k++)
dp[l][r] = min(dp[l][r], dp[l][k - 1] + a[k] * a[l - 1] * a[r + 1] + dp[k + 1][r]);
}
}
printf("%lld", dp[2][n - 1]);
return 0;
}