题解：P12148 【MX-X11-T2】「蓬莱人形 Round 1」所以我放弃了音乐

江湖午餐票 · 2025-04-12 19:30:48 · 题解

题目大意

在一个无限大的棋盘上有 n 个棋子，每次操作可以选择一个起点并按特定规则删除连续棋子。求删除所有棋子所需的最少操作次数。

操作规则：

1. 选择格子 (x,y)，若此处有棋子则删除
2. 依次检查 (x+1,y+1)、(x+1,y)、(x+1,y-1)，找到第一个有棋子的格子并重复操作。

解题思路

每个操作实际上形成一条从起点向右下方延伸的路径。最优策略是将棋子组织成尽可能多的连续路径。

个人感觉数有多少条路径的实现比较麻烦，此处我们可以逆向思考一下：若无法形成连续路径，则需要 n 次操作，而每形成一对棋子的配对就可以减少一次的操作，那么我们只需要求出棋子的配对数 c，答案就是 n-c。

此处需要注意每个棋子只能有一个与其配对的棋子，我就是卡在这了……

代码

实现的时候脑回路比较清奇，等重构后再贴上来吧 （可能到五一都不一定会重构）