专栏文章

题解：P13439 [GCJ 2009 #1C] Bribe the Prisoners

FFreezing_Winter
P13439题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3nysp
此快照首次捕获于
2025/12/02 12:50
3 个月前
此快照最后确认于
2025/12/02 12:50
3 个月前
查看原文
传送门
三倍经验：P1622 和 SP14846。
然后因为 RMJ 寄了 SP 的经验吃不到了现在又成双倍了。

思路

可搭配它一起食用。
算了再说句闲话：狱警贿赂囚犯也是猎天下之大奇。
一眼区间 DP。
先设计下状态：设 dpi,jdp_{i,j} 为释放区间 [i,j][i,j] 内囚犯贿赂最小代价。
然后易得状态转移方程为：
dpi,j=min⁡k=ij(dpi,k−1+dpk+1,j+aj+1−ai−1−2)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})
关于 min⁡\min
式子
min⁡i=xyai\min\limits_{i=x}^ya_i
等同于
min⁡(ax,ax+1,...,ay−1,ay)\min(a_x,a_{x+1},...,a_{y-1},a_y)
其中 aia_i 表示第 ii 个需要释放的囚犯编号。
蓝色部分为释放囚犯 aka_k 前所需最小代价，红色部分为释放囚犯 aka_k 所需最小代价。
由于释放 aka_k 会将全场分为 [i,k−1][i,k-1] 和 [k+1,j][k+1,j] 两个独立的区间，所以
为什么红色部分是 aj+1−ai−1−2a_{j+1}-a_{i-1}-2 呢？
很简单，释放 aka_k 时，需贿赂 [ai−1+1,ak−1]∪[ak+1,aj+1−1][a_{i-1}+1,a_k-1]\cup[a_k+1,a_{j+1}-1] 的所有囚犯，代价为：
(ak−ai−1−1)+(aj+1−ak−1)=aj+1−ai−1−2(a_k-a_{i-1}-1)+(a_{j+1}-a_k-1)=a_{j+1}-a_{i-1}-2
最后思考初始值，很明显：
  • 当 i>ji>j 时，dpi,j=0dp_{i,j}=0，因为此时 [i,j]=∅[i,j]=\varnothing，无任何囚犯需要释放。
  • 当 i≤ji\le j 时，dpi,jdp_{i,j} 默认为 inf⁡\inf。
答案为 dp1,Qdp_{1,Q}，即释放区间 [1,Q][1,Q] 内所有囚犯的最小代价。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...