#4744. 「KTSC 2019 R2」多边形 题解

题目理解

这是一个多边形构造优化问题：给定由 L（左转）和 R（右转）组成的字符串，构造一个满足特定条件的正交多边形（只有水平和垂直边），使得该多边形的最小外接矩形面积最小。

关键约束：

• 多边形必须由水平和垂直边组成
• 任意垂直线与多边形水平边内部最多有2个交点
• 起始点总是最左边边的上方顶点，且第一个字符总是 L
• 边长必须为整数

核心算法

算法标签：动态规划 几何构造 状态压缩 最优化

1. 问题分析

多边形行走规则

• L：逆时针方向左转90°
• R：逆时针方向右转90°
• 由于是正交多边形，每次转向后行走方向在 {上, 右, 下, 左} 中循环

关键观察

• 多边形是闭合的，N次转向后应回到起点
• 最小外接矩形面积 = (最大x - 最小x) × (最大y - 最小y)
• 需要找到一种坐标分配方案，使得这个面积最小

2. 算法思路

坐标建模

将多边形行走建模为二维网格上的路径：

• 初始位置：(0,0)，方向：右（根据题意，第一个L表示从左边开始向上）
• 每个字符决定下一步的行走方向
• 最终必须回到原点 (0,0)

动态规划状态设计

设 dp[i][x][y][dir] 表示处理完前i个字符，当前位置为(x,y)，面向方向为dir时的某种状态。

由于N最大为800，直接四维DP不可行，需要优化：

优化思路：

1. 相对坐标：记录相对于起始点的位置变化
2. 方向序列：利用转向序列的周期性
3. 状态剪枝：排除不可能回到原点的状态

3. 面积最小化策略

边界计算

外接矩形面积由路径的极值点决定：

• min_x, max_x：x坐标的最小最大值
• min_y, max_y：y坐标的最小最大值

面积 = (max_x - min_x + 1) × (max_y - min_y + 1)

搜索策略

由于直接DP状态空间太大，可能采用：

• 迭代加深搜索
• meet-in-middle
• 启发式搜索

算法正确性分析

为什么这样能保证多边形合法性？

1. 正交性：每次转向90°，保证边为水平或垂直
2. 闭合性：最终必须回到原点
3. 交点限制：通过合理的坐标分配避免垂直线与过多水平边相交

关键技巧

• 坐标压缩：通过相对坐标减少状态空间
• 对称性利用：多边形具有某种对称性
• 可行性剪枝：提前排除无法闭合的路径

复杂度分析

• 状态空间：$O(N^3)$ 或 $O(N^2 \times \text{常数})$ 经过优化
• 实际运行：在 $N \leq 800$ 时可行
• 记忆化搜索：避免重复计算

算法标签总结

主要标签

• 动态规划 - 核心算法框架
• 几何构造 - 问题领域
• 状态优化 - 关键技术

技术标签

• 坐标建模 - 将转向序列映射为坐标
• 最值维护 - 跟踪边界坐标
• 路径搜索 - 在状态空间中寻找最优解

优化标签

• 状态压缩 - 减少DP状态数
• 剪枝策略 - 提前终止不可能分支
• 记忆化搜索 - 避免重复计算

几何算法标签

• 多边形构造 - 根据转向序列构建几何形状
• 外接矩形 - 面积计算
• 正交多边形 - 特殊多边形类型

关键创新点

1. 转向序列解析：将L/R序列转化为几何行走
2. 闭合条件处理：确保路径最终回到原点
3. 面积最优化：在满足所有约束下最小化外接矩形
4. 状态空间管理：在较大N值下仍能高效求解

样例验证

样例1：LLLRRLLL → 面积6

• 字符串长度8
• 通过合理的坐标分配，得到最小外接矩形面积6
• 可能对应3×2的矩形

样例2：LLRLLRRLLRLLRLLRRLLR → 面积15

• 字符串长度20
• 更复杂的转向模式
• 最小外接矩形面积15（如3×5或5×3）

这个解法通过巧妙的状态设计和优化，解决了正交多边形的最小外接矩形面积优化问题。