这道题我首先想到的爆搜骗点分,
五分钟的代码,
结果全T了,
不太行 >_<
====手动分割=====
正片开始
这题我没有看别人的代码就知道是区间DP
众所周知,区间DP大部分都用f[i][j]
这道题我们可以用f[i][j]表示i点和j点之间的点已经被删除
那么我们就需要用之前的最优状态来推导出f[i][j]
那么之前的状态是什么呢??
好好想一想
显然就是i和j中间有一个点需要删除,
那么也就是说,上一个状态时,i,j之间存在一个K,我们需要把k删掉来得到我们的f[i][j]
那么我们就可以循环一下k,看看哪一个k作为上一个状态最合适
(人人为我)
代码如下,勿抄
#include <iostream>
using namespace std;
const int N = 101;
int n;
int a[N];
int f[N][N];
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int len = 3;len <= n;len ++)
{
for(int l = 1;l + len - 1 <= n;l ++)
{
int r = l + len - 1;
for(int k = l + 1;k < r;k ++)
{
f[l][r] = max(f[l][r],f[l][k] + f[k][r] + a[k] * a[l] * a[r]);
}
}
}
cout << f[1][n];
}