题解：SP14846 GCJ1C09C - Bribe the Prisoners

Freezing_Winter · 2025-08-28 15:32:59 · 题解

传送门

三倍经验：P1622 和 P13439。

思路

可搭配它一起食用。

区间 DP 变式题。

约定数组 a，a_i 表示第 i 个需要释放的囚犯编号。

设 dp_{i,j} 为释放区间 [i,j] 囚犯所需最小代价，易得转移方程：

其中 x=dp_{i,k-1}+dp_{k+1,j}，y=a_{j+1}-a_{i-1}-2。

由于释放 a_k 后，会将区间 [i,j] 分为 [i,k-1] 和 [k+1,j] 两个相对独立的区间，因此释放 a_k 前所需最小代价为 x。

而释放 a_k 时，需贿赂区间 [a_{i-1},a_k-1] 和 [a_k+1,a_{j+1}] 内的所有囚犯。因此成本为：

最后考虑初始状态：

• 当 i>j 时，dp_{i,j}=0。
• 当 i\le j 时，dp_{i,j}=\inf。

最终答案即为 dp_{1,Q}。