loj 10151. 「一本通 5.1 练习 2」分离与合体

题目链接

一道比较裸的区间 dp

设状态 $f_{l,r}$ 为合并到 $[l,r]$ 时获得的最大价值，那么对于 $l \le k \le r$ 有

$$f_{l,r} = \max\Big( f_{l,r}, \; f_{l,k} + f_{k+1,r} + (a_l + a_r) \cdot a_k \Big)$$

枚举时按照区间 dp 的顺序，先枚举区间长度，再枚举左右端点，接着枚举区间范围内的数进行合并转移。

---

分离顺序的输出

题目还要求出分离顺序。我们可以在转移时：

• 如果枚举到的区间合并方案 优于先前方案（即可以更新区间答案）
• 那么记录下
  $p_{l,r} = k$
  表示区间 $[l,r]$ 从 $k$ 位置分离。

接着：

• 开一个 vector<int> 数组
• 每一个 vector 存储 某一层 的分离位置
• 然后递归扫描每一层区间，将分离位置 push_back 到对应层的 vector 中
• 输出时把每一层的分离位置 sort 后，从小到大输出即可

---

Code

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 305;

int n, a[maxn], f[maxn][maxn], p[maxn][maxn], dep;
vector<int> ans[maxn];

void makePrint(int l, int r, int dep) {
    if (l == r) return;                 // 递归终止条件
    ::dep = max(dep, ::dep);            // 记录下最大层数
    ans[dep].push_back(p[l][r]);
    makePrint(l, p[l][r], dep + 1);     // 递归搜索下一层
    makePrint(p[l][r] + 1, r, dep + 1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int l = 0; l <= n; l++) {
        for (int i = 1, j = i + l; j <= n; i++, j++) {
            for (int k = i; k < j; k++) {
                if (f[i][k] + f[k + 1][j] + (a[i] + a[j]) * a[k] > f[i][j]) {
                    f[i][j] = f[i][k] + f[k + 1][j] + (a[i] + a[j]) * a[k];
                    p[i][j] = k;        // 记录区间的分离位置
                }
            }
        }
    }

    printf("%d\n", f[1][n]);

    makePrint(1, n, 1);                 // 递归将每一层的分离位置加入 vector

    for (int i = 1; i <= dep; i++)
        sort(ans[i].begin(), ans[i].end());   // 对每一层排序

    for (int i = 1; i <= dep; i++) {     // 按层数优先输出
        int sz = ans[i].size();
        for (int j = 0; j < sz; j++)
            printf("%d ", ans[i][j]);
    }
    putchar('\n');

    return 0;
}