闫式dp分析
技巧
- 能量石
读入中三个数字表示两个能量石,中间数字既前一个能量石的尾部标记,又表示后一个能量石的头部标记,所以应该计算每
n + 1
个数释放的能量,从中取得最大值。
- 环链展开为两倍长度单链
将环形的能量石展开为两倍长度的单链能量石
结果与初始化
- 初始化
求最大值,所以应该初始化为负无穷,这里使用
0
表示负无穷,因为每个能量石都会释放出非负的能量。由于至少存在三个数字才能释放能量,所以只有一个数字或两个数字时,无法释放能量,所以初始化为0
。这里的0
是没有能量释放出来,并不代表负无穷。
- 结果
最终的结果应该在区间长度为
n + 1
的某个区间,所以遍历所有长度为n + 1
的区间,取最大值。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;
int f[N][N];
int w[N];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> w[i];
w[i + n] = w[i];
}
for(int len = 1; len <= n + 1; len ++)
for(int i = 1; i + len - 1 <= n * 2; i ++)
{
int j = i + len - 1;
for(int k = i + 1; k < j; k ++)
f[i][j] = max(f[i][j], f[i][k] + f[k][j] + w[i] * w[j] * w[k]);
}
int ans = 0;
for(int i = 1; i <= n; i ++)
ans = max(ans, f[i][i + n]);
cout << ans << endl;
return 0;
}