题解：SP14846 GCJ1C09C - Bribe the Prisoners

三倍经验：P1622 和 P13439。

可搭配它一起食用。

区间 DP 变式题。

约定数组

a

，

a_i

表示第

i

个需要释放的囚犯编号。

设

dp_{i,j}

为释放区间

[i,j]

囚犯所需最小代价，易得转移方程：

dp_{i,j}=\min\limits_{k=i}^j(x+y)

其中

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}]

内的所有囚犯。因此成本为：

(a_k-a_{i-1}-1)+(a_{j+1}-a_k-1)=a_{j+1}-a_{i-1}-2=y

最后考虑初始状态：

最终答案即为

dp_{1,Q}

。

文章操作