[IOI 1998] Polygon

形式化题目

给定一个 $n$ 个顶点的环。第 $i$ 个顶点带整数权值 $a_i$ ，第 $i$ 条边带运算符 $op_i \in \{+, \times\}$ ，且边 $i$ 连接顶点 $i$ 与顶点 $i+1$ （下标模 $n$ ，顶点 $n+1$ 即顶点 $1$ ）。

一次操作：任选一条还存在的边 $e$ ，它连接顶点 $u, v$ ，把 $u, v$ 合并成一个新顶点，新顶点的权值为 $a_u \operatorname{op}_e a_v$ ，同时删去 $e$ 。

游戏的第一步必须先删掉任意一条边而不做合并；之后一直操作，直到只剩一个顶点，它的权值就是本局得分。

求所有「第一步删的边 + 之后的合并顺序」中能得到的最高分，并输出所有第一步删掉后能取到该分数的最小边编号集合（按编号递增，形如 1 2）。

约束： $3 \leqslant n \leqslant 50$ ，任意时刻顶点权值落在 $[-32768, 32767]$ 。

解法路线

直接模拟「每一步合并哪一对」有 $(n-1)!$ 量级的搜索树， $n=50$ 时完全不可行；必须找到一个能把指数搜索压成多项式、且能安全处理 乘法让正负翻转 的状态设计。

层次	适用约束	做法	复杂度	相对前层的推进
暴力枚举合并顺序	$n \leqslant 8$	枚举第一步删的边，再递归枚举之后每步合并哪一对相邻顶点	$O(n!)$	基线，只用于小数据对拍
朴素区间 DP（只存最大值）	无负数或运算符全为 `+`	把环展开成链，`f[l][r]` 只存区间合并后的最大值	$O(n^3)$	用「最后一次合并的断点」取代逐步枚举，把指数搜索压成多项式；但乘法下会出错
双状态区间 DP	$n \leqslant 50$	每个区间同时存最大值 `f[l][r]` 和最小值 `g[l][r]`，乘法时枚举四种极值组合	$O(n^3)$	补上最小值，使「负 × 负 = 正」这类能产生更大值的路径不被漏掉
正解：双状态 DP + 枚举断边	$n \leqslant 50$	对每条断边各展开一次链做双状态 DP，取全局最优，所有能得到最优值的断边按编号升序输出	$O(n^4)$	用「枚举断边」消掉环的循环依赖

表后的关键跳跃有两处：一是把逐步合并换成「最后一次合并的断点」，这是区间 DP 的典型形态；二是乘法下只保留最大值不够，必须同时保留最小值。环则由「枚举断边 + 展开成链」处理， $O(n^4) = 50^4 \approx 6 \times 10^6$ 完全可接受。

暴力解法

思路

照着题意模拟：先枚举第一步删掉哪条边 $b$ ，把剩下的 $n$ 个顶点、 $n-1$ 条边按顺序排成一条链；之后每一步任选链上一对相邻顶点合并（运算符换成它们的运算结果），递归直到只剩一个顶点，这个值就是一种可能的得分。

每层递归都按值传一份「当前链」的副本再合并，不做回溯恢复，避免下标写错。

代码

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/**
 * 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-23 23:09
 * update_at: 2026-10-24 00:50
 */
// brute.cpp：小数据暴力解，用来理解题意并和 main.cpp 对拍。
// 做法：枚举第一步删掉的边 b，把剩下的 n 个顶点、n-1 条边展开成一条链，
// 然后枚举这条链上所有合并顺序（每步任选一对相邻顶点合并），取叶子处的最大值。
// 复杂度 O(n!)，只适合 n <= 8 的小数据。
// 实现上每层递归都按值传一个「当前链」的副本，不做回溯恢复，避免下标写错。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 64;

int n;
int v[maxn];    // v[i]：第 i 个顶点（输入第 i 组里的那个数），1..n
char op[maxn];  // op[i]：第 i 条边（输入第 i 组里的那个运算符），1..n

ll best_score;          // 目前找到的最高分
vector<int> best_edges; // 能达到最高分的所有第一步删除边（递增、去重）

// 链：pr_v[p] 是链上第 p 个顶点的权值，pr_op[p] 是链上第 p 与 p+1 个顶点之间的运算符
// 用 vector 按值传递，递归里各层互不影响
ll dfs(vector<int> pr_v, vector<char> pr_op) {
    if (pr_v.size() == 1) return pr_v[0];
    ll best = LLONG_MIN;
    for (int p = 0; p + 1 < (int)pr_v.size(); p++) {
        vector<int> nv(pr_v);
        vector<char> no(pr_op);
        ll val = (no[p] == 'x') ? (ll)nv[p] * nv[p + 1] : (ll)nv[p] + nv[p + 1];
        nv[p] = (int)val;
        nv.erase(nv.begin() + p + 1);
        no.erase(no.begin() + p);
        best = max(best, dfs(nv, no));
    }
    return best;
}

// 删除第 break_id 条边，把环展开成链，然后枚举该链的全部合并顺序，返回最高分
ll solve_break(int break_id) {
    // 链上第 p 个顶点 = 输入第 (break_id+p-1) mod n + 1 号顶点，
    // 链上第 p 条边   = 输入第 (break_id+p-1) mod n + 1 号边（依次 op[break_id+1], ...）
    // 与 main.cpp 的 build_chain 完全一致
    vector<int> pr_v;
    vector<char> pr_op;
    for (int p = 0; p < n; p++) {
        int id = (break_id - 1 + p) % n + 1;
        pr_v.push_back(v[id]);
        if (p < n - 1) {
            int eid = (break_id + p) % n + 1;   // 链上第 1 条边是 op[break_id+1]
            pr_op.push_back(op[eid]);
        }
    }
    return dfs(pr_v, pr_op);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> op[i] >> v[i];

    best_score = LLONG_MIN;
    for (int b = 1; b <= n; b++) {
        ll cur = solve_break(b);
        if (cur > best_score) {
            best_score = cur;
            best_edges.clear();
            best_edges.push_back(b);
        } else if (cur == best_score) {
            best_edges.push_back(b);
        }
    }

    cout << best_score << "\n";
    for (int i = 0; i < (int)best_edges.size(); i++) {
        if (i) cout << " ";
        cout << best_edges[i];
    }
    cout << "\n";
    return 0;
}

复杂度

每条断边对应 $(n-1)!$ 种合并顺序，共 $n$ 条断边； $n=8$ 时共 $8 \times 7! = 40320$ 个叶子，可以接受， $n=50$ 则不可行。

瓶颈

暴力把「第几步合并哪一对」当成决策，决策序列的数量是阶乘级的。要压缩它，需要换一个刻画问题的方式：不问「第一步」，而是问最后一步。

朴素尝试：只存最大值的区间 DP

沿用「最后一次合并的断点」的区间切分（详见下一节），先只保留最大值 $H[l][r]$ ，转移为 $H[l][r] = \max_k \left( H[l][k]\ \text{op}_k\ H[k+1][r] \right)$ ，边界 $H[i][i] = v_i$ 。复杂度 $O(n^3)$ ，比暴力快得多。

只要运算符全是 +，它就是对的：加法单调，每一段取最大就好。但题目里还有 x，且权值可为负数，这时它会给出错答案（具体反例见「只存最大值会在乘法下出错」一节）。所以这一层本身不是合格的正解，但它是通往下一步的必经台阶。

正解

关键观察：从「每一步」换成「最后一次合并」

固定一条断边、把环展开成链 $v_1, v_2, \dots, v_n$ ，边 $k$ 连接 $v_k$ 与 $v_{k+1}$ （ $1 \leqslant k < n$ ）。

无论前面的合并怎么进行，最后一次合并一定是把某个前缀区间 $[l, k]$ 的结果与后缀区间 $[k+1, r]$ 的结果用边 $k$ 合并起来。而这两个区间内部怎样合并、互不影响——它们各自又是一个同型的子问题。于是可以得到区间 DP：

状态： $F[l][r]$ = 把链上区间 $[l,r]$ 合并成一个顶点时能得到的最大值。
转移：枚举最后一条被用的边 $k \in [l, r-1]$ ，则
$F[l][r] = \max_{k} \bigl( F[l][k] \operatorname{op}_k F[k+1][r] \bigr)$
边界： $F[i][i] = v_i$ 。

这已经把 $O(n!)$ 的搜索压成 $O(n^3)$ （ $O(n^2)$ 个区间、每个区间 $O(n)$ 个断点），对照 P1880 石子合并的形态完全一样。

瓶颈：只存最大值会在乘法下出错

如果运算符只有 +，上面的 $F$ 就足够：加法单调，大的一定更好。但题目里有 x（乘法），只要出现负数，「最大值」就立刻不够用。

看一条具体的链（ $n=6$ ，顶点 $-3,3,1,-5,5,-4$ ，边 t,t,x,t,x）：

区间 $[l,r]$	只存最大值的 $H[l][r]$	真正的最大值	真正的最小值
$[1,5]$	$0$	$0$	$-18$
$[6,6]$	$-4$	$-4$	$-4$
$[1,6]$	$0$ （错）	$72$	$-103$

差在哪里：区间 $[1,6]$ 的最后一条边是 $k=5$ （运算符 x），它把 $[1,5]$ 的结果乘上 $[6,6] = -4$ 。 $[1,5]$ 的最小值是 $-18$ ，因为 $-18 \times (-4) = 72$ 成了全区间最大值；而 $[1,5]$ 的最大值 $0$ 只能乘出 $0 \times (-4) = 0$ 。只存最大值的 DP 把 $H[1,5] = 0$ 往上传，于是 $H[1,6] = 0$ ，与真值 $72$ 相差甚远。

一句话概括：

乘法的极值一定由两个子区间各自的极值相乘得到（双线性函数在矩形四角取极值）；
但「负 × 负」会翻正，所以两个最负的负数相乘可能才是最大值，区间的最小值必须一起保留。

因此每个区间必须同时记住最大值和最小值。

思路：双状态区间 DP

把上面的观察落成转移。对链上区间 $[l,r]$ ，记：

$F[l][r]$ ：合并成单点后的最大值；
$G[l][r]$ ：合并成单点后的最小值。

枚举最后一条边 $k$ 时：

若 $op_k$ 是 +：加法单调， $F[l][r] \leftarrow F[l][k] + F[k+1][r]$ ， $G[l][r] \leftarrow G[l][k] + G[k+1][r]$ ；
若 $op_k$ 是 x：只可能是四种极值组合之一，
$\{F[l][k]F[k+1][r],\ F[l][k]G[k+1][r],\ G[l][k]F[k+1][r],\ G[l][k]G[k+1][r]\}$
取最大者进 $F$ 、最小者进 $G$ 。

正确性论证（对区间长度归纳）：设区间 $[l,r]$ 的任意一种合并方案，其最后一步必然用某条边 $k$ 合并 $[l,k]$ 与 $[k+1,r]$ 的成果 $x, y$ 。由归纳假设， $x \in [G[l][k], F[l][k]]$ 、 $y \in [G[k+1][r], F[k+1][r]]$ 。若 $op_k$ 为 +， $x+y$ 在两端点取极值，即由 $F+F$ 、 $G+G$ 取得；若为 x， $xy$ 是双线性函数，在矩形四个角上取极值，恰为上面四种组合。所以真实极值一定被枚举到，转移不会漏解；又每种组合都对应一个合法方案，也不会多算。按区间长度从小到大递推即可。

样例断边 1（链 $[-7,4,2,5]$ ，边 t,x,x）的完整 DP 表：

区间	$F$ （最大）	$G$ （最小）
$[1,1]$	$-7$	$-7$
$[2,2]$	$4$	$4$
$[3,3]$	$2$	$2$
$[4,4]$	$5$	$5$
$[1,2]$	$-3$	$-3$
$[2,3]$	$8$	$8$
$[3,4]$	$10$	$10$
$[1,3]$	$1$	$-6$
$[2,4]$	$40$	$40$
$[1,4]$	$\mathbf{33}$	$\mathbf{-30}$

注意 $[1,4]$ 的最大值 $33$ 来自断点 $k=1$ ： $[1,1] = -7$ 与 $[2,4] = 40$ 用 t 相加， $(-7) + 40 = 33$ 。而 $[2,4] = 40$ 本身是用 $[2,2]=4$ 与 $[3,4]=10$ 相乘； $[3,4]=10 = 2 \times 5$ 。也就是「先算 $2\times5$ ，再乘 $4$ ，最后加 $-7$ 」。

破环成链与断边选取

环上的难点是首尾相连， $[l,r]$ 的转移会绕回来。这里用最直白的处理：枚举第一步删掉哪条边 $b$ ，环就被切断成一条长度为 $n$ 的链，再无循环依赖。

实现里把输入第 $i$ 组读作「第 $i$ 条边 $op_i$ 、第 $i$ 号顶点 $v_i$ 」。删掉第 $b$ 条边后（下表 $p = 1,2,\dots,n$ ）：

链上第 $p$ 个顶点是输入第 $(b+p-2) \bmod n + 1$ 号顶点（依次 $v_b, v_{b+1}, \dots$ 循环）；
链上第 $p$ 条边是输入第 $(b+p-1) \bmod n + 1$ 号边（从 $op_{b+1}$ 开始，因为 $op_b$ 已被删掉）。

用样例校准：输入为 t -7 t 4 x 2 x 5，即 $op_1..op_4 = $ `t`,`t`,`x`,`x`、$ v_1…v_4 = -7,4,2,5$。断边 $b=1$ （删掉 t）时， $p=1$ 的顶点号为 $(1+1-2) \bmod 4 + 1 = 1$ 、边号为 $(1+1-1) \bmod 4 + 1 = 2$ ，于是链是 $-7,4,2,5$ ，边依次 t,x,x——正是样例推演所需的那条链。

对每条 $b$ 各跑一次双状态 DP，记 $best_b = F[1][n]$ 。答案取 $\max_b best_b$ ；第二行输出所有使 $best_b$ 等于该最大值的 $b$ 。按 $b = 1, 2, \dots, n$ 的顺序遍历并输出，就已经是题目要求的递增顺序，不需要额外排序，也不会漏掉任何一条最优断边。

代码

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
115
116
117
118/**
 * 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-23 23:09
 * update_at: 2026-10-24 09:40
 */
// main.cpp：P4342 [IOI 1998] Polygon 正解。
// 破环成链 + 双状态区间 DP：对每条断边各跑一次区间 DP，取最高分，并把所有取到最高分的断边按编号升序输出。
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 105;

int n;
int v[maxn];      // v[i]：输入第 i 组给的顶点权值（顶点 i 在环上）
char op[maxn];    // op[i]：输入第 i 组给的运算符，'t' 表示 +，'x' 表示 *

int chain_v[2 * maxn];     // chain_v[p]：断点 break_id 展开成链后，第 p 个顶点的权值
char chain_op[2 * maxn];   // chain_op[p]：链上顶点 p 与 p+1 之间的运算符

ll f[2 * maxn][2 * maxn]; // f[i][j]：区间 [i,j] 合并成一个顶点时，权值的最大值
ll g[2 * maxn][2 * maxn]; // g[i][j]：区间 [i,j] 合并成一个顶点时，权值的最小值

// 把原环按断边 break_id 展开成链。
// 输入按「op[i] v[i]」成对给出，v[i] 是第 i 号顶点，op[i] 是第 i 号边。
// 断掉第 break_id 条边后：
//   链上第 p 个顶点 = 输入第 (break_id+p-2) mod n + 1 号顶点（依次 v[break_id], v[break_id+1], ...）；
//   链上第 p 条边   = 输入第 (break_id+p-1) mod n + 1 号边（依次 op[break_id+1], op[break_id+2], ...）。
// 注意顶点与边的下标错开一位：删掉的是边 break_id，所以顶点从 break_id 起、边从 break_id+1 起。
// 这套下标对应关系与题目样例（33 / 1 2）及 IOI'98 官方五组测试的答案完全一致。
void build_chain(int break_id) {
    for (int p = 1; p <= n; p++) {
        int vertex_id = ((break_id + p - 2 + n) % n) + 1;
        chain_v[p] = v[vertex_id];
        if (p < n) {
            int edge_id = ((break_id + p - 1) % n) + 1;   // 链上第 1 条边是 op[break_id+1]
            chain_op[p] = op[edge_id];
        }
    }
}

// 对当前链做双状态区间 DP，把整条链合并成一个顶点后的最大/最小权值写入 best_max / best_min
// f[i][j] 只保留最大值、g[i][j] 只保留最小值：乘法的极值一定来自两个子区间极值的组合
void solve_chain(ll &best_max, ll &best_min) {
    for (int i = 1; i <= n; i++) {
        f[i][i] = chain_v[i];
        g[i][i] = chain_v[i];
    }
    for (int len = 2; len <= n; len++) {        // 区间长度从小到大，保证子区间已算好
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            f[i][j] = LLONG_MIN;
            g[i][j] = LLONG_MAX;
            for (int k = i; k < j; k++) {       // 最后一步：把 [i,k] 与 [k+1,j] 用第 k 条边合并
                ll left_max = f[i][k], left_min = g[i][k];
                ll right_max = f[k + 1][j], right_min = g[k + 1][j];
                ll val[4];
                int cnt = 0;
                if (chain_op[k] == 't') {       // 加法：极值来自两个子区间各自的极值
                    val[cnt++] = left_max + right_max;
                    val[cnt++] = left_min + right_min;
                } else {                        // 乘法：四种极值组合里必含真正的最大值与最小值
                    val[cnt++] = left_max * right_max;
                    val[cnt++] = left_max * right_min;
                    val[cnt++] = left_min * right_max;
                    val[cnt++] = left_min * right_min;
                }
                for (int t = 0; t < cnt; t++) {
                    if (val[t] > f[i][j]) f[i][j] = val[t];
                    if (val[t] < g[i][j]) g[i][j] = val[t];
                }
            }
        }
    }
    best_max = f[1][n];
    best_min = g[1][n];
}

void read_data(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i] >> v[i];    // 输入按「边 1 的运算符、顶点 1 的权值、边 2 的运算符、…」交错给出
    }
}

void solve(){
    ll answer = LLONG_MIN;
    ll best[maxn];              // best[break_id]：删掉第 break_id 条边后能得到的最高分
    for (int break_id = 1; break_id <= n; break_id++) {
        build_chain(break_id);
        ll cur_max = 0, cur_min = 0;
        solve_chain(cur_max, cur_min);
        best[break_id] = cur_max;
        if (cur_max > answer) answer = cur_max;
    }

    // 第二行：所有能取到最优分数的第一步删除边，按编号递增输出
    cout << answer << "\n";
    bool first = true;
    for (int break_id = 1; break_id <= n; break_id++) {
        if (best[break_id] == answer) {
            if (!first) cout << " ";
            cout << break_id;
            first = false;
        }
    }
    cout << "\n";
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();
    solve();
    return 0;
}

复杂度

每条断边做一次 $O(n^3)$ 的双状态区间 DP，共 $n$ 条断边，总时间 $O(n^4)$ ，空间 $O(n^2)$ 。 $n \leqslant 50$ 时约 $6 \times 10^6$ 次转移，远在时限内（实测 $n=50$ 的随机数据 $0.02$ s 内出解）。

总结

本题是「区间 DP + 环形处理」的组合模板：先用「最后一次合并的断点」把逐步枚举压成区间 DP，再补上最小值这一维以处理乘法的符号翻转，最后用「枚举断边」把环展开成链。三个步骤都链式地解决了上一层留下的具体障碍——搜索树爆炸、乘法下极值不可传递、环的首尾依赖。代码实现上注意三点：负无穷/正无穷初值要足够小/大、乘法用 long long 防溢出、断边输出遍历顺序即为升序。

目录