有 n
个数字 a1,a2,…,an
，我们要把除了 a1,an
之外的其他数字删除，删除一个数字的代价是它乘上它相邻两个还没有被删除的数字的值，请求出最小代价是多少。
输入格式
第一行一个整数 n
。
接下来一行 n
个整数 a1,a2,…,an
。
输出格式
一个整数，表示答案。
样例输入
5
5 6 4 2 7
样例输出
178
数据规模
对于所有数据，保证 1≤n,ai≤500
。
区间DP
注意这次分段不是dp[i][k]和dp[k+1][j]而是dp[i][k]和dp[k][j]
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N],f[N][N];
int main()
{
int n;
cin>>n;
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;++i) {cin>>a[i];f[i][i]=0;f[i][i+1]=0;}
for(int l=3;l<=n;++l)
for(int i=1;i<=n;++i)
{
int j=i+l-1;
if(j>n) break;
for(int k=i;k<j;++k)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]*a[j]*a[k]);
}
cout<<f[1][n]<<'\n';
}