(一) 先提取对象、变量、限制和目标
读题时可以先写下面四项:
| 项目 | 要回答的问题 | 示例 |
|---|---|---|
| 对象 | 要处理哪些东西? | n 件物品、m 个区间、一个字符串 |
| 变量 | 哪些值已知,哪些值需要求? | 已知高度 h[i],求符合条件的数量 |
| 限制 | 哪些操作或状态合法? | 每件只能选一次、两人不能用同一个位置 |
| 目标 | 最终输出什么? | 是否存在、方案数、最小花费、具体方案 |
不要把故事中的无关信息都存入程序。例如“仓库有不同颜色的盒子”,如果颜色不影响规则,通常就不需要颜色变量。
数据范围也是题意的一部分。 正数与任意整数会影响滑动窗口的单调性;边权是否非负会影响最短路算法;能否重复选择会影响背包转移方向。
把原要求翻译成约束之后,还要分别证明必要性和充分性;后面会给出完整程序。