形式化题目

$n$ 个区域排成一行，区域 $i$ 上金钥匙的价值为 $a_i$。对一段连续区域 $[l..r]$（$l < r$）可以在区域 $k$（$l \leqslant k < r$，即区间末尾除外）处做一次分离：在 $k$ 与 $k+1$ 之间升起隔墙，把 $[l..r]$ 切成 $[l..k]$ 与 $[k+1..r]$ 两段，两段各自继续分离，直到每段只剩一个区域。随后自底向上合体：每把在 $k$ 处分离的 $[l..r]$ 两半重新合并，获得收益

从 $[1..n]$ 出发完成整棵分离-合体过程，求总收益的最大值；并按分离阶段从前到后、同一阶段内区域从左到右的顺序输出所有发生过分离的区域编号；若有多个最大方案，输出序列字典序最小的一个。

样例：$n = 7$，$a = [1,2,3,4,5,6,7]$，最大收益 $238$，输出序列 1 2 3 4 5 6。

正解

思路

一句话本质：一次分离把连续区间劈成互不干扰的左右两半，收益只与"本区间两端 + 本刀切点"有关——把问题从"枚举整棵分离树"换成"枚举一段区间的第一个切点"，就是区间 DP。

朴素做法与瓶颈。 最直接的想法是枚举整棵分离树：根在 $k$ 处切开，递归枚举左右两半的所有形状与切点，逐树求和取最大。方案数是 Catalan 级别，$n = 300$ 时不可想象。慢的根源不是"求和"，而是重叠子问题：同一段连续区域 $[l..r]$ 的最优分离方式只取决于这段区域本身——它出现在树的哪一层、外层怎么切，都不影响它内部的收益。指数枚举把同一个区间的最优值重复算了指数多次。

关键观察：收益按区间分解。 记 $[l..r]$ 为一段连续区域：

1. 在 $k$ 处分离的这一刀收益 $(a_l + a_r) \cdot a_k$ 只用到本区间两个端点和切点，与两半内部如何继续分离无关；
2. 左右两半的收益各自落在互不相交的子区间里：任何一层切分都把区间分成不重叠的两段，且权值全为正。

于是任意方案的总收益 = 各区间收益之和，两半各自取最优，整体就最优（最优子结构）。自底向上看，本区间的"最后一个决策"就是它的第一个切点 $k$。

状态与转移。 设 $dp[l][r]$ 表示把区域段 $[l..r]$ 全部分离再合体能获得的最大收益（0-based，代码中 $l, r$ 从 $0$ 开始）：

单个区域无法分离，收益为 $0$。$[l..k]$ 与 $[k+1..r]$ 都比 $[l..r]$ 短，按长度 $len = 2, 3, \dots, n$ 递推，用到的子状态天然已经算出；答案是 $dp[0][n-1]$。

样例 DP 表。 下表是样例的全部 $dp$（行 = 左端点 $l$，列 = 右端点 $r$，- 表示 $l > r$ 的无效格，对角线是边界值 $0$；单元格 = 最大收益 / 取到最大收益的最左切点，切点用 1 基编号）：

观察重点：越靠右上，区间越长，每格只依赖更短的区间；每行的切点都等于该区间的左端点，说明样例的最优分离树是一条向右生长的链。右上角 $dp[1][7]$ 的六个候选：

链上每一刀的收益依次是 $(1+7)\cdot 1 = 8$、$(2+7)\cdot 2 = 18$、$(3+7)\cdot 3 = 30$、$(4+7)\cdot 4 = 44$、$(5+7)\cdot 5 = 60$、$(6+7)\cdot 6 = 78$，合计 $8+18+30+44+60+78 = 238$，与样例第一行一致；每层恰有一个切点，层序输出就是 1 2 3 4 5 6。

记录切点：平手取最左。 转移枚举 $k$ 时从左到右、只在候选值严格更大时替换，平手自然保留最左的 $k$，记进 $cut[l][r]$。例如 $n=3$、$a = [1,1,1]$ 时 $dp[1][3]$ 的 $k=1$ 与 $k=2$ 都得到 $4$，按要求取 $k=1$，输出序列是 1 2 而不是 2 1。

为什么"每个区间各自取最左"就得到全局字典序最小？ 由收益分解，任何最优方案里出现的每个区间都必须取到该区间的最优切点（哪个区间没取到自己的最大值，总收益就不是最大），所以"最优方案" = "给每个可达区间各指定一个最优切点"的独立组合。层序输出的下一个数只由当前这个区间决定：它前面的数来自更浅层或更靠左的区间、已经固定；它后面的数来自更深或更靠右的区间、还没确定。按字典序比较的贪心性质，当前区间取最小的可行值（最左最优切点）不会让整体序列变差，递归到每个区间都成立。

输出序列：层序重建。 题面说的"分离阶段"就是分离树的深度层：根的那次分离是阶段 1，之后每个区间的分离都紧跟在其父区间之后的阶段进行。从根区间 $[0..n-1]$ 开始 BFS：弹出 $[l..r]$ 就输出 $cut[l][r]+1$，左右子区间长度 $\geqslant 2$ 时入队。同一深度的区间在数轴上互不相交、从左到右，父结点先入队、左孩子先于右孩子入队，因此出队顺序恰好是"阶段从早到晚、同阶段从左到右"。

层序与常见的前序（DFS）不同。构造一个小例子 $a = [10,2,7,2,5,7]$（最大收益 $392$）来看，它的最优分离树是：

1
2
3
4
5
6
7
8
9
10
111..6 分离于 5
|- 1..5 分离于 3
|  |- 1..3 分离于 1
|  |  |- 1..1 叶子
|  |  `- 2..3 分离于 2
|  |     |- 2..2 叶子
|  |     `- 3..3 叶子
|  `- 4..5 分离于 4
|     |- 4..4 叶子
|     `- 5..5 叶子
`- 6..6 叶子

按分离阶段分层：阶段 1 是 5，阶段 2 是 3，阶段 3 是 1 4，阶段 4 是 2，输出 5 3 1 4 2；若按前序输出则会是 5 3 1 2 4——更深但更靠左的 2 必须排在更浅但更靠右的 4 后面，这正是"阶段从前到后、同层从左到右"的要求。

正确性。 对区间长度归纳：长度为 $1$ 时 $dp = 0$ 显然。一般情形下，由观察 1 任意方案都唯一对应它的根切点 $k$，由观察 2 该方案的收益 = 两半的收益 + 本刀收益，不同 $k$ 对应互不相交的方案集合；枚举全部 $k$ 且两半取各自最优，覆盖所有方案、不重不漏，故 max 即全局最优。层序重建读出的正是这棵最优树的全部切点。

边界。 长度为 $2$ 的区间只有 $k = l$ 一个候选（best 初值取 $-1$，候选恒为正，不会被初值污染）；单区域区间不再分离、不入队；$n = 1$ 时两层循环与队列都不执行，输出 0 与空序列（题面数据 $n \geqslant 2$）。权值与结果都在 32 位正整数范围内，Python 的 int 天然不溢出。

代码

plan_separations() 递推价值表与切点表，solve() 取 dp[0][n-1] 作答案，walk_levels() 对切点表做层序重建。

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 19:18
# update_at: 2026-09-30 19:18

import sys
from collections import deque


def plan_separations(a: list[int]) -> tuple[list[list[int]], list[list[int]]]:
    """区间 DP：dp[l][r] 是区间 [l, r] 分离-合体的最大总价值，cut[l][r] 记录取到最大值的最左分离点。"""
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    cut = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):  # 短区间先算，转移只依赖更短的区间
        for l in range(n - length + 1):
            r = l + length - 1
            ends = a[l] + a[r]  # 合体收益里的“区间左右端点价值之和”
            best, best_k = -1, l
            for k in range(l, r):  # 从左往右枚举，严格大于才替换：平手取最左分离点
                total = dp[l][k] + dp[k + 1][r] + ends * a[k]
                if total > best:
                    best, best_k = total, k
            dp[l][r], cut[l][r] = best, best_k

    return dp, cut


def walk_levels(cut: list[list[int]]) -> list[int]:
    """把分离树按分离阶段（层）从左到右走一遍，产出各分离点的 1 基区域编号。"""
    n = len(cut)
    order: list[int] = []
    queue: deque[tuple[int, int]] = deque([(0, n - 1)] if n > 1 else [])
    while queue:
        l, r = queue.popleft()
        k = cut[l][r]
        order.append(k + 1)
        if l < k:  # 左子区间长度 >= 2 才还需要再分离
            queue.append((l, k))
        if k + 1 < r:  # 右子区间长度 >= 2 才还需要再分离
            queue.append((k + 1, r))
    return order


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]  # 0 基化：a[i] 是区域 i+1 的金钥匙价值
    dp, cut = plan_separations(a)
    print(dp[0][n - 1])
    print(' '.join(map(str, walk_levels(cut))))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:17
 * update_at: 2026-10-05 09:17
 */

// 区间 DP：dp[l][r] 表示把区间 [l..r] 全部分离再合体的最大总价值，
// 转移枚举本区间的第一个分离点 k：dp[l][r] = max_k { dp[l][k] + dp[k+1][r] + (a_l + a_r) * a_k }。
// 输出要求字典序最小：枚举 k 从左到右、严格大于才替换，平手自然取最左切点；
// 再从根区间按分离阶段（层序）遍历切点表，即得"阶段从前到后、同阶段从左到右"的输出。

#include <cstdio>

typedef long long ll;

const int MAXN = 305;

int n;
ll a[MAXN];        // a[i]：第 i 个区域金钥匙的价值（1 基）
ll dp[MAXN][MAXN]; // dp[l][r]：区间 [l..r] 分离-合体的最大总价值
int cut[MAXN][MAXN]; // cut[l][r]：取到最大值的最左分离点（1 基）

// 区间 DP 递推：按区间长度从小到大，保证转移用到的子区间已算好
void plan_separations() {
    for (ll len = 2; len <= n; ++len) {
        for (ll l = 1; l + len - 1 <= n; ++l) {
            ll r = l + len - 1;
            ll ends = a[l] + a[r]; // 合体收益里的"区间左右端点价值之和"
            ll best = -1;
            ll best_k = l;
            // 从左往右枚举切点，严格大于才替换：平手保留最左，保证字典序最小
            for (ll k = l; k < r; ++k) {
                ll total = dp[l][k] + dp[k + 1][r] + ends * a[k];
                if (total > best) {
                    best = total;
                    best_k = k;
                }
            }
            dp[l][r] = best;
            cut[l][r] = best_k;
        }
    }
}

// 输出序列重建：把分离树按层（分离阶段）BFS，同一层内区间从左到右
// 由于父子入队有序（父先入队、左孩子先于右孩子），出队顺序恰好满足题目要求
void walk_levels() {
    int head = 0;
    int tail = 0;
    static int ql[MAXN * MAXN]; // 队列存区间左端点
    static int qr[MAXN * MAXN]; // 队列存区间右端点
    if (n < 2) return; // 单个区域无法分离
    ql[tail] = 1; qr[tail] = n; ++tail;
    bool first = true;
    while (head < tail) {
        ll l = ql[head];
        ll r = qr[head];
        ++head;
        ll k = cut[l][r];
        if (!first) printf(" ");
        printf("%lld", k);
        first = false;
        // 左右子区间长度 >= 2 时才需要继续分离，入队
        if (l < k) { ql[tail] = l; qr[tail] = k; ++tail; }
        if (k + 1 < r) { ql[tail] = k + 1; qr[tail] = r; ++tail; }
    }
    printf("\n");
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    plan_separations();
    printf("%lld\n", dp[1][n]);
    walk_levels();
    return 0;
}

复杂度

• 时间复杂度：区间状态 $O(n^2)$ 个，每个状态枚举 $O(len)$ 个切点，总转移次数 $\sum_{len=2}^{n}(n-len+1)(len-1) = \binom{n+1}{3} \approx n^3/6$。$n = 300$ 时约 $4.5 \times 10^6$ 次内层运算，实测最大一组 0.26 s、峰值约 18 MB——与标准 C++ 的 $O(n^3)$ 解法同阶。
• 空间复杂度：价值表与切点表各一张 $n \times n$，加上 $O(n)$ 的层序队列，共 $O(n^2)$；$n = 300$ 只有约 $9 \times 10^4$ 个格子。

总结

• 连续区间 + “切成互不干扰的两半” + 端点型收益 → 区间 DP；关键观察是收益按区间分解、互不重叠，最优子结构与重叠子问题同时成立。
• $dp[l][r]$ 枚举本区间第一个切点 $k$，按长度递推，答案 $dp[0][n-1]$；朴素枚举整棵分离树是 Catalan 级，区间 DP 把它降到 $O(n^3)$。
• 输出字典序最小的切点序列 = “平手取最左” + “从根层序遍历”：前者保证每个区间选最左的最优切点，后者保证阶段从前到后、同阶段从左到右。
• 代码里 total > best 的严格比较是字典序的来源；把 > 改成 >= 会翻转成最右切点，输出序列随之改变。

图示解析

这张图串起本题从建模到输出的主线：

1
2
3
4
5
6
7一次分离把连续区间切成左右两半
|- 本刀收益 = (区间两端权值和) × 切点权值，两半收益互不重叠
|  `- 最优子结构 + 重叠子问题 → 区间 DP：枚举本区间第一个切点 k
|     `- dp[l][r] = max_k { dp[l][k] + dp[k+1][r] + (a_l + a_r)·a_k }
`- 输出要求字典序最小
   `- 枚举 k 从左到右、严格大于才替换 → 每个区间记录最左最优 cut
      `- 从根区间层序遍历 → 阶段从前到后、同阶段从左到右

先看左侧分支如何从"收益分解"推出转移方程，再看右侧分支如何把字典序要求落成"平手取最左 + 层序输出"；两条分支在 cut 表处汇合——它既是 DP 的决策记录，也是输出序列的唯一数据源。