10 lines
630 B
Markdown
10 lines
630 B
Markdown
# P4342 [IOI 1998] Polygon 题解
|
|
|
|
题意：给定一个环，节点上有权值，边上有运算符 $\times$ 或 $+$，断掉一条边，按一定顺序合并相邻两个点，求最大结果以及能够达到最大结果的第一次断边选择。
|
|
|
|
显然第一步要破环成链，将序列复制两遍，开一个大小为 $n$ 的滑动窗口来枚举断边。
|
|
|
|
显然要区间 dp。最初想到用 $f_{l, r}$ 表示 $[l, r]$ 最大值，但是发现负数 $\times$ 负数可能成为新的最大值。因此考虑同时记录 $g_{l, r}$ 表示 $[l, r]$ 的最小值。随后分类讨论转移即可。
|
|
|
|
[code](../P4342.cpp)
|