P12588 「KTSC 2019 R2」多边形

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include int polygon(std::string S); ``` 题目译自 [2019년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2019/) T4「[다각형](https://assets.ioikorea.kr/ioitst/2019/1/polygon/polygon_statement.pdf)」

考虑一个由水平和垂直边组成，并有 $N$ 个顶点的多边形 $P$。多边形 $P$ 的边只能在端点相交，每个顶点正好有两条边的端点相交。当沿着多边形 $P$ 的边逆时针移动时，会在顶点处向左或向右转弯。如果在顶点处向左转弯，用 $\texttt{L}$ 表示；向右转弯，则用 $\texttt{R}$ 表示。这样就可以用 $\texttt{L}$ 和 $\texttt{R}$ 组成的字符串来表示多边形。例如，图 1 中的多边形可以用字符串 $$\texttt{LLRLLRRLLRLLRLLRRLLR}$$ 表示。用字符串表示多边形时，字符串的起始位置总是多边形最左边边的上方顶点。这个字符总是 $\texttt{L}$。  用给定字符串表示的多边形需要满足以下条件：对于任意垂直线 $V$，$V$ 在多边形水平边的内部（不包括端点）最多只能有 $2$ 个交点。 对于多边形 $P$，其包含的最小水平和垂直边组成的矩形记为 $B(P)$。它由多边形 $P$ 的最左、最右、最上和最下边与矩形的垂直和水平线重合（见图 2）。  给定由字母 $\texttt{L}$ 和 $\texttt{R}$ 组成的长度为 $N$ 的字符串，绘制这个字符串表示的满足上述条件的多边形 $P$。此时，多边形 $P$ 的边长为整数。编写一个程序，使 $B(P)$ 的面积最小，并输出其最小值。 你需要为管理员实现以下一个函数： - `int polygon(string S);` 接受长度为 $N$ 的字符串 $S$ 作为参数。字符串 $S$ 的每个字符是 $\texttt{L}$ 或 $\texttt{R}$。函数需要找到字符串 $S$ 表示的多边形 $P$ 中使 $B(P)$ 的面积最小的情况，并返回这个最小面积。 函数必须按照上述描述进行操作。当然，你可以创建和使用其他函数，但不得进行任何输入输出操作或访问其他文件。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$，表示字符串的长度 - 第 $2$ 行：长度为 $N$ 的字符串 $c_{1} c_{2} \cdots c_{N}$，其中 $c_{1}=\texttt{L}, c_{i}=\texttt{L}$ 或 $\texttt{R} (2 \leq i \leq N)$

示例评测程序会输出 `polygon` 函数的返回值。

对于所有输入数据，满足： - 输入字符串仅包含字母 $\texttt{L}$ 或 $\texttt{R}$ - 表示上述条件的多边形的输入字符串总是存在至少一个 - $4 \leq N \leq 800$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :----------: | :----------: | :----------: | |$1$|$20$|$N \leq 10$| |$2$|$36$|$N \leq 40$| |$3$|$21$|$N \leq 100$| |$4$|$73$|无附加限制|