闫式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;
}