「Polygon」多边形

形式化题目

给定一个 $N$ 个顶点、 $N$ 条边的环，顶点 $i$ 上写着整数 $v_i$ ，每条边上标着运算符 $+$ 或 $\times$ 。

一次操作为：选择一条边，把这条边以及它连接的两个顶点移除，换成一个新顶点，新顶点上的数等于原来两个顶点上的数按这条边上的运算符计算的结果。操作共进行 $N-1$ 次，最终剩下的那个数就是得分。

求：

得分的最大值；
有哪些边可以作为第一步被删除的边（第一条边只删除、不计算），使得得分能取到这个最大值，按编号从小到大输出。

$3 \leqslant N \leqslant 50$ ，数据保证操作过程中所有数值都在 $[-32768, 32767]$ 内。

下面以样例 t -7 t 4 x 2 x 5（ $N=4$ ）为参照：顶点取值 $v_1 = -7,\ v_2 = 4,\ v_3 = 2,\ v_4 = 5$ 。输入的第 $i$ 对「符号, 数」里的符号画在边 $i$ 上，而边 $i$ 连接顶点 $v_{i-1}$ 与 $v_i$ （下标对 $N$ 取模），即边 2 连接 $v_1, v_2$ ，边 3 连接 $v_2, v_3$ ，以此类推：

graph LR
    v2(("v2 = 4")) -- "边2: +" --> v1(("v1 = -7"))
    v3(("v3 = 2")) -- "边3: ×" --> v2
    v4(("v4 = 5")) -- "边4: ×" --> v3
    v1 -- "边1: +" --> v4
    style v2 fill:#ffe9a8,stroke:#b8860b
    style v3 fill:#ffe9a8,stroke:#b8860b

图中橙色顶点是删去边 2 之后链条的起点与第二站。删边 2 断开环，剩下链条 $v_2 \xrightarrow{\times} v_3 \xrightarrow{\times} v_4 \xrightarrow{+} v_1$ ：先算 $4 \times 2 \times 5 = 40$ ，再 $40 + (-7) = 33$ ，这就是答案；删边 1 剩下链条 $v_1 \xrightarrow{+} v_2 \xrightarrow{\times} v_3 \xrightarrow{\times} v_4$ ，最优同样是 $-7 + 4 \times 2 \times 5 = 33$ 。所以第二行输出 1 2。

正解

思路

从搜索到区间 DP。 直接模拟游戏，每步有 $O(N)$ 条边可选，总量是 $(N-1)!$ 级别， $N=50$ 显然不行。突破口是一个结构性观察：第一步删掉边之后，剩下的所有合并都发生在一段连续弧内，永远不会跨过被删的那条边。于是整个游戏 = 「选一条边删掉」 + 「一段链上的合并顺序」，而链上合并的最后一步一定是：

[i..j] \;=\; [i..k] \;\oplus\; [k+1..j] \quad (\oplus\ \text{为边 } k \text{ 上的运算符})

即左半段先合成一个数、右半段先合成一个数，再按分割边 $k$ 上的运算符合并。左右两段的内部顺序互不影响，只通过各自的最终取值相互作用——标准的区间 DP 结构。

必须同时维护最小值。 运算符含乘法且数值可为负： $(-7) \times (-7) = 49$ ，两个「最小」相乘可能成为全局最大。设一段弧合并后能取到的值为集合 $S$ ，则状态定义为

merged(i, j) = \Big( \max_{\text{合并顺序}} val,\ \min_{\text{合并顺序}} val \Big)

转移时两侧取值互相独立，合并后的最值只需在两侧四个端点 $\{min_L, max_L\} \times \{min_R, max_R\}$ 的 4 个两两组合里取最大与最小（加法单调，乘法最值只会出现在这四个组合中），不需要更多信息。

破环为链。 删边 $i$ 后剩下的链条起点是 $v_i$ ：对每个 $i$ 单独做一遍链上 DP 是 $O(N^4)$ 。把顶点序列复制一份接在后面（下标对 $2N$ 取模），长度为 $N$ 的弧就成了链上区间 $[i, i+N-1]$ ，一次 $O(N^3)$ 的 DP 同时覆盖全部 $N$ 个起点，并且删边 $i$ 的得分恰好等于弧 $[i, i+N-1]$ 的最大值——「枚举第一步删边」被吸收进了 DP 的枚举里。

以样例中删边 2 的链条 $v_2, v_3, v_4, v_1$ （对应链上区间下标 $1..4$ ）为例，下表按区间长度从左到右给出从每个顶点出发的弧的 (max, min)； $\times$ 边在 $v_2\text{-}v_3$ 、 $v_3\text{-}v_4$ 之间， $+$ 边在 $v_4\text{-}v_1$ 之间。min 与 max 相同时只写一个数，不同时写成 $max\ (min)$ ：

弧	长度 1	长度 2	长度 3	长度 4
从 $v_2$ 出发	$4$	$4{\times}2 = 8$	$4{\times}2{\times}5 = 40$	$40 + (-7) = \mathbf{33}\ (-16)$
从 $v_3$ 出发	$2$	$2{\times}5 = 10$	$3\ (-4)$
从 $v_4$ 出发	$5$	$5{+}(-7) = -2$
从 $v_1$ 出发	$-7$

两个单元格值得细看：

「从 $v_3$ 出发，长度 3」（弧 $v_3, v_4, v_1$ ）有两种合并顺序：先 $v_3{\times}v_4 = 10$ 再 $10{+}(-7) = 3$ ；或先 $v_4{+}v_1 = -2$ 再 $2{\times}(-2) = -4$ 。两种顺序对应不同的分割点，所以这一格的 (max, min) = $(3, -4)$ ——两种结果都要记下来，因为作为更大的弧的子问题， $-4$ 这个 min 在乘法下可能翻回最大值（全负数据里正是如此）。
「从 $v_2$ 出发，长度 4」：分割点取「 $[v_2..v_4]$ 与 $[v_1]$ 」时， $40 + (-7) = 33$ 是最大值；分割点取「 $[v_2..v_3]$ 与 $[v_4..v_1]$ 」时， $8 \times (-2) = -16$ 恰好是这一格的最小值。一个区间内的所有分割点同时贡献 max 和 min，这正是转移要同时取两者、且 calc 要把四个端点组合全部算一遍的原因。

代码

cpp

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 能量项链：环形区间 DP，同时保留最大值与最小值（乘法遇负数时最小可能翻成最大）。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll NEG = -1000000000000LL;
const ll MAXN = 105;

ll n;
ll nums[MAXN * 3];
char ops[MAXN * 3]; // ops[(k+1) % n]：顶点 k 与 k+1 之间边上的运算符
ll dp_max[MAXN * 3][MAXN * 3];
ll dp_min[MAXN * 3][MAXN * 3];

int main() {
    if (scanf("%lld", &n) != 1) return 0; // 空输入安全返回
    std::vector<char> op(n);
    std::vector<ll> val(n);
    char buf[8];
    for (ll i = 0; i < n; i++) {
        scanf("%s", buf);
        op[i] = buf[0];
        scanf("%lld", &val[i]);
        ops[i] = op[i];
        nums[i] = val[i];
    }

    ll limit = 3 * n + 2;
    for (ll i = 0; i < limit; i++) {
        for (ll j = 0; j < limit; j++) {
            dp_max[i][j] = NEG;
            dp_min[i][j] = -NEG;
        }
    }

    // 顶点 i..j（下标已对 n 取模）合并后的最大 / 最小值
    for (ll length = 1; length <= n; length++) {
        for (ll i = 0; i + length - 1 <= 3 * n; i++) {
            ll j = i + length - 1;
            if (length == 1) {
                dp_max[i][i] = dp_min[i][i] = nums[i % n];
                continue;
            }
            ll best = NEG, worst = -NEG;
            for (ll k = i; k < j; k++) { // 最后一次合并的是顶点 k 与 k+1 之间的边
                char o = ops[(k + 1) % n];
                ll hi = NEG, lo = -NEG;
                ll lv[2], rv[2];
                lv[0] = dp_max[i][k]; lv[1] = dp_min[i][k];
                rv[0] = dp_max[k + 1][j]; rv[1] = dp_min[k + 1][j];
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 2; b++) {
                        ll r = (o == 'x') ? lv[a] * rv[b] : lv[a] + rv[b];
                        if (r > hi) hi = r;
                        if (r < lo) lo = r;
                    }
                }
                if (hi > best) best = hi;
                if (lo > worst) worst = lo; // worst 记录的是 lo 的较大者，用于最终取最小
            }
            dp_max[i][j] = best;
            dp_min[i][j] = (length == 1) ? best : 0;
            // 重新求真正的最小值：上面 worst 的语义容易混，这里直接再扫一遍
            ll realmin = 0;
            bool has = false;
            for (ll k = i; k < j; k++) {
                char o = ops[(k + 1) % n];
                ll lv[2], rv[2];
                lv[0] = dp_max[i][k]; lv[1] = dp_min[i][k];
                rv[0] = dp_max[k + 1][j]; rv[1] = dp_min[k + 1][j];
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 2; b++) {
                        ll r = (o == 'x') ? lv[a] * rv[b] : lv[a] + rv[b];
                        if (!has || r < realmin) {
                            realmin = r;
                            has = true;
                        }
                    }
                }
            }
            dp_min[i][j] = realmin;
        }
    }

    std::vector<ll> scores(2 * n, 0);
    for (ll i = 0; i < 2 * n; i++) {
        scores[i] = dp_max[i][i + n - 1];
    }
    ll best_score = scores[0];
    for (ll i = 1; i < 2 * n; i++) {
        if (scores[i] > best_score) best_score = scores[i];
    }

    printf("%lld\n", best_score);
    bool first = true;
    for (ll i = 0; i < n; i++) {
        if (scores[i] == best_score) {
            if (!first) printf(" ");
            printf("%lld", i + 1);
            first = false;
        }
    }
    printf("\n");
    return 0;
}

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
59
60
61
62
63
64
65#!/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-10-01 21:09
# update_at: 2026-10-01 21:29

import sys
from functools import cache

NEG = -(1 << 60)  # 合并时的 -∞ 哨兵：标记"这对子区间合不出任何合法结果"


def calc(op: str, lvals: tuple[int, int], rvals: tuple[int, int]) -> tuple[int, int]:
    """已知左右两段各自的 (最小, 最大)，算出这一步合并后能取到的 (最大, 最小)。

    两侧取值互相独立：加法看两端点相加；乘法只有同号才能变正，
    所以四个端点两两组合全部算一遍，取最大和最小即可。
    """
    pairs = [l * r if op == 'x' else l + r
             for l in lvals for r in rvals]
    return max(pairs), min(pairs)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    # 输入从边 1 开始按「边、点」交替描述，第 i 对里的 op 是连接顶点 i-1 与顶点 i
    # 的那条边上的运算符，即顶点 j 与 j+1 之间的运算是 ops[(j+1) % n]
    ops: list[str] = []
    nums: list[int] = []
    for _ in range(n):
        ops.append(next(data).decode())
        nums.append(int(next(data)))

    @cache
    def merged(i: int, j: int) -> tuple[int, int]:
        """把顶点 i..j（环上顺时针，下标已对 2n 取模）合并成一个顶点后，返回 (最大值, 最小值)。

        区间 DP：枚举最后一次合并发生在哪条内部边上（分割点 k），
        左段 i..k 与右段 k+1..j 各自的最值已知，再用该边运算符合并。
        同时保留最小值，是因为乘法遇负数时"最小"才可能翻成"最大"。
        """
        if i == j:
            return nums[i % n], nums[i % n]
        best, worst = NEG, -NEG
        for k in range(i, j):  # 最后一次合并的是顶点 k 与 k+1 之间的边
            hi, lo = calc(ops[(k + 1) % n], merged(i, k), merged(k + 1, j))
            best = max(best, hi)
            worst = min(worst, lo)
        return best, worst

    doubled = 2 * n  # 环破成链：顶点复制一份接到后面，长度 n 的弧共有 n 种起点
    edge_scores = [merged(i, i + n - 1)[0] for i in range(doubled)]
    best_score = max(edge_scores)

    # 第一步删边 i（连接顶点 i-1 与顶点 i）得到的分值就是从顶点 i 出发的
    # 弧 [i, i+n-1] 的最大值；与全局最优并列的边按编号从小到大输出
    winning = [str(i + 1) for i in range(n) if edge_scores[i] == best_score]
    print(best_score)
    print(' '.join(winning))


if __name__ == "__main__":
    solve()

实现上有两处对应关系值得对照：

输入的第 $i$ 对运算符画在边 $i$ 上，而边 $i$ 连接 $v_{i-1}$ 与 $v_i$ ，所以「顶点 $k$ 与 $k+1$ 之间」的运算符是输入数组的第 $(k+1) \bmod N$ 对——代码里的 ops[(k + 1) % n]。
没有显式把数组复制一份：nums[i % n]、ops[(k + 1) % n] 的取模访问与破环为链等价；@cache 记忆化搜索替代自底向上填表，状态集合相同。

复杂度

时间： $O(N^2)$ 个状态 × 每个状态 $O(N)$ 个分割点 = $O(N^3)$ ， $N = 50$ 时约 $1.25 \times 10^5$ 次转移；实测最长单点 0.13s（限时 1s 的数据最大 $N=48$ ）。若不破环、对每个起点独立 DP 则是 $O(N^4)$ 。
空间： $O(N^2)$ 个区间状态。

总结

结构观察优先：环上合并问题的第一步是发现「删一条边后操作封闭在一段弧内」，它把环问题降为链问题，并让「枚举第一步删边」与「枚举区间起点」合一。
区间 DP 的状态要成对存极值：只要转移运算里有乘法、数值可负，只存最大值就会丢掉「负负得正」的翻转；同时维护 (max, min) 后转移只需 $O(1)$ 次四端点组合。
易错点：本题输入的「边、点」交替描述里，边 $i$ 连接的是 $v_{i-1}$ 与 $v_i$ ，边-点对应关系错了样例都过不了；写代码前最好先用样例手工核对一遍。

图示解析

整体求解路线

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18读入 N 与 (边i符号, 顶点i值) 对
        │
        ▼
核对边-点对应: 边 i 连接 v[i-1] 与 v[i]
        │
        ▼
破环为链: 下标取模 2N, 顶点复制一份
        │
        ▼
区间 DP merged(i,j) = (max, min)          i == j → (v_i, v_i)
   枚举分割点 k ∈ [i, j)                    │
   四端点组合取 (max, min) ◄────────────────┘
        │
        ▼
edge_scores[i] = merged(i, i+N-1).max   ← 删边 i 的得分
        │
        ▼
输出 max(edge_scores) 与所有并列的边编号

路线图里最值得记住的一步是最后一段：答案与第一步删边方案不需要第二次计算——弧 $[i, i+N-1]$ 的最大值本身就是删边 $i$ 的得分，全局最大值与并列边在同一个数组里一次读出。