AcWing 320 能量项链

一、数据样例解析

第二行是\(N\)个用空格隔开的正整数，所有的数均不超过 \(1000\)，第 \(i\) 个数为第 \(i\) 颗珠子的头标记，当 \(i<N\) 时，第 \(i\) 颗珠子的尾标记应该等于第 \(i+1\) 颗珠子的头标记，第 \(N\) 颗珠子的尾标记应该等于第 \(1\) 颗珠子的头标记。

上面这段话，就是告诉我们，其实，是一个首尾相连接的环。

样例： \(2\) \(3\) \(5\) \(10\)
表示有\(4\)个珠子：\(①[2,3]\), \(②[3,5]\),\(③[5,10]\),\(④[10,2]\)

如果我们先合并的\(④\)和\(①\),最终结果就是\(⑤[10,3]\)，释放能量\(10*2*3=60\)点，剩下\(②③⑤\)
\(⑤\)再与\(②\)合并，结果就是\(⑥[10,5]\)，释放能量\(10*3*5=150\)点。剩下\(③\)和\(⑥\)
\(⑥\)与\(③\)合并，结果就是\(⑦[10,10]\)，释放能量\(10*5*10=500\)点。剩下\(⑦\),只剩下一个了，完成！
一共合并\(3\)次，总的能量就是\(60+150+500=710\)点

二、理解题意

本题是上一题环形石子合并问题的变形，或者说更类似于矩阵连乘问题。按照上一题一样的处理环形问题的方法，将序列的长度翻倍。

状态表示
\(f[l][r]\)表示第\(l\)到第\(r\)个数合并释放的最大能量

这里注意比如\(len\)为\(3\)时，\(2\) \(3\) \(5\)实际上只是两颗珠子包含的信息，即\(（2,3）\)和\(（3,5）\)因此合并\(2\) \(3\) \(5\)释放的能量等于\(2 * 3 *5\)。

最后剩下一棵珠子的头尾吸盘也需要合并到一起的，比如\(2\) \(3\) \(5\) \(10\)合并成为了\((2,10)\)，尽管此时合并成了一串，但项链的首尾仍需要连接，所以还需要合并\((2,10)\)及\((10,2)\)，本题就转化成了求区间长度为\(n + 1\)的石子合并问题的最大值。

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 210;//开两倍的空间
int n;
int w[N];
int f[N][N];    //左，右端点间的能量最大值
int main() {
    cin >> n;
    //环形DP的标准路线，双倍长度，w[i+n]=w[i]
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i + n] = w[i];
    }
    //因为最后需要扣头，所以区间长度是n+1
    //长度是3才能构成两个珠子，才能对接释放能量
    for (int len = 3; len <= n + 1; len++)           //枚举有效区间长度
        for (int l = 1; l + len - 1 <= n * 2; 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] + w[l] * w[r] * w[k]);
        }
    //枚举所有区间长度是n+1的区间，取一个最大值
    int res = 0;
    for (int i = 1; i <= n; i++)//枚举每个左端点，长度为n+1的区间，能量最大值是多少
        res = max(res, f[i][i + n]);
    //输出 
    printf("%d", res);
    return 0;
}