Oiclass P1266 题解

这道题绝对称得上是 DP Ultra

So, what is DP Ultra ? The answer is: 环形区间 DP ！！！！！！！真的离谱！！！

1. 划分阶段

一共有 \(2 \times n\) 个阶段，每个阶段表示 \(i\) 开始 \(j\) 结束的区间里面一共最多能产生多少能量。

2. 定义状态变量

直接搞一个万能二维数组 \(f\) ， \(f_{i,\ j}\) 表示一个阶段，也就是表示 \(i\) 开始 \(j\) 结束的区间里面一共最多能产生多少能量

3. 写出状态转换方程

这里用递归来解，func(int x, int y) 就是本次的主角——递归函数。为了尽量优化，这里使用了记忆化的方法进行剪枝（用于记忆的是二维数组 \(f\)），速度还行吧，至少没超时，对于函数体。如果 \(x=y\) 那么直接退出，毕竟全部遍历完了，如果 \(f_{x,\ y}\) 已经有值，那么直接返回就行，如果都不行，那么进行计算，计算需要便利 \(x \to y\) 的每一个点，然后通过方程计算他的值，取所有值的最大值即可，用于计算的公式如下： \[ f_{x,\ y}=\max(f_{x,\ y}, func(x, i) + func(i + 1, y) + a_x * a_{i + 1} * a_{y + 1}); \]

4. 边界条件

边界条件是这道题目最为良心的了，因为头尾相同的时候，最大值一定为 \(0\) ，毕竟一颗珠子都没有，所以这个题目的边界条件就是： \[ f_{i,\ i}=0 \] 因为他 \(=0\) 所以很庆幸，我们不需要对数组进行任何操作，初始值就是 \(0\)，大妙了

5. 实现

实现绝非易事，首先要考虑到这个东西是项链！！也就是环，那么我们采用经典的破环为链的方法（高情商），也可以说是用数组模拟一个环（低情商），简单说就是把数组镜像一遍贴在原数组的尾部（Ctrl - C + Ctrl - V），也就形成了一个主观上的环型了。为了形成这个环形，我们的数组实际上存储了 \(2 \times n\) 个数据，虽然听起来时间空间翻倍，但是这已经是最优解了。计算的时候我们首先遍历 \(a_{1 \to n}\) 的每一个位置，调用函数 func(i, i + n - 1) 计算当前起点的最大值，然后将其与目前存储的最大值比较，得到新的最大值，在函数内部，我们用 （3）中提到的逻辑进行计算，同时使用记忆化的方式进行剪枝，避免空间时间双爆的满江红。下面看一下代码：

#include <iostream>

using namespace std;

int n, ans = -2147483647, a[1000009], f[5009][5009];

int func(int x, int y) {
    if (x == y) {
        return 0;
    }
    if (f[x][y]) {
        return f[x][y];
    }
    for (int i = x; i < y; i++) {
        f[x][y] = max(f[x][y], func(x, i) + func(i + 1, y) + a[x] * a[i + 1] * a[y + 1]);
    }
    return f[x][y];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, func(i, i + n - 1));
    }
    cout << ans;
}