Louis Aeilot's Blog
·
題解 P1622 釋放囚犯
💡
原文中文，约2100字，阅读约需5分钟。
📝
内容提要
求释放所有罪犯的最小费用，区间DP，状态转移方程为f[l][r] = min of f[l][m-1] + f[m+1][r] + Pos[r+1] - Pos[l-1] -2，输出f[1][Q]。
🎯
关键要点
- Caima王国有P个牢房，监狱满员。
- 每天释放名单上的一个人，释放后会引起其他囚犯的不满。
- 需要给不满的囚犯送肉以安抚他们。
- 输入包括P和Q，Q为释放人数，后面是释放的囚犯编号。
- 输出为最少需要送肉的次数。
- 使用区间动态规划求解，状态f[l][r]表示从l到r号囚犯释放所需的肉块总数。
- 状态转移方程为f[l][r] = min of f[l][m-1] + f[m+1][r] + Pos[r+1] - Pos[l-1] - 2。
- Pos数组用于存储囚犯编号，Pos[Q+1] = P + 1。
➡️
