题解：P13439 [GCJ 2009 #1C] Bribe the Prisoners
Freezing_Winter
·
·
题解
传送门
三倍经验：P1622 和 SP14846。
然后因为 RMJ 寄了 SP 的经验吃不到了现在又成双倍了。
思路
可搭配它一起食用。
算了再说句闲话：狱警贿赂囚犯也是猎天下之大奇。
一眼区间 DP。
先设计下状态：设 dp_{i,j} 为释放区间 [i,j] 内囚犯贿赂最小代价。
然后易得状态转移方程为：
dp_{i,j}=\min\limits_{k=i}^{j}(\color{blue}dp_{i,k-1}+dp_{k+1,j}\color{black}+\color{red}a_{j+1}-a_{i-1}-2\color{black})
::::info[关于 \min]
式子
\min\limits_{i=x}^ya_i
等同于
\min(a_x,a_{x+1},...,a_{y-1},a_y)
::::
其中 a_i 表示第 i 个需要释放的囚犯编号。
蓝色部分为释放囚犯 a_k 前所需最小代价，红色部分为释放囚犯 a_k 所需最小代价。
由于释放 a_k 会将全场分为 [i,k-1] 和 [k+1,j] 两个独立的区间，所以
为什么红色部分是 a_{j+1}-a_{i-1}-2 呢？
很简单，释放 a_k 时，需贿赂 [a_{i-1}+1,a_k-1]\cup[a_k+1,a_{j+1}-1] 的所有囚犯，代价为：
(a_k-a_{i-1}-1)+(a_{j+1}-a_k-1)=a_{j+1}-a_{i-1}-2
最后思考初始值，很明显：
- 当 i>j 时，dp_{i,j}=0，因为此时 [i,j]=\varnothing，无任何囚犯需要释放。
- 当 i\le j 时，dp_{i,j} 默认为 \inf。
答案为 dp_{1,Q}，即释放区间 [1,Q] 内所有囚犯的最小代价。