題解 P1622 釋放囚犯
Caima 王國中有一個奇怪的監獄，這個監獄一共有 $P$ 個牢房，這些牢房一字排開，第 $i$ 個緊挨著第 $i+1$ 個（最後一個除外）。現在正好牢房是滿的。
上級下發了一個釋放名單，要求每天釋放名單上的一個人。這可把看守們嚇得不輕，因為看守們知道，現在牢房中的 $P$ 個人，可以相互之間傳話。如果某個人離開了，那麼原來和這個人能說上話的人，都會很氣憤，導致他們那天會一直大吼大叫，搞得看守很頭疼。如果給這些要發火的人吃上肉，他們就會安靜點。
第一行兩個整數 $P$ 和 $Q$，$Q$ 表示釋放名單上的人數；
第二行 $Q$ 個整數，表示要釋放哪些人，保證按遞增的順序給出。
僅一行，表示最少要給多少人次送肉吃。
1
2
20 3
3 6 14
1
35
先釋放 $14$ 號監獄中的罪犯，要給 $1$ 到 $13$ 號監獄和 $15$ 到 $20$ 號監獄中的 $19$ 人送肉吃；再釋放 $6$ 號監獄中的罪犯，要給 $1$ 到 $5$ 號監獄和 $7$ 到 $13$ 號監獄中的 $12$ 人送肉吃；最後釋放 $3$ 號監獄中的罪犯，要給 $1$ 到 $2$ 號監獄和 $4$ 到 $5$ 號監獄中的 $4$ 人送肉吃。
- 對於 $50\%$ 的資料，$1 \le P \le 100$，$1 \le Q \le 5$；
- 對於 $100\%$ 的資料，$1 \le P \le 10^3$，$1 \le Q \le 100$，$Q \le P$，保證釋放的人所在的牢房編號按遞增的順序給出。
題意即求釋放列表中所有罪犯的費用之和最小，每次釋放，罪犯i到他兩邊空牢房之間的所有人，都需要消耗一塊肉。每次釋放一個罪犯，可以想到區間 DP，狀態 f[l][r] 表示從l到r號罪犯全部釋放所需要消耗的肉塊總數。
之後思考狀態轉移方程。要求最小值，f[l][r] 初始值 INT_MAX。f[l][r] = min of f[l][m-1] + f[m+1][r] + Pos[r+1] - Pos[l-1] -2 ，其中 m 屬於區間 [l,r]，列舉合併點，即此次釋放的罪犯，罪犯兩側到l和r號罪犯的消耗f[l][m-1]和f[m+1][r]。Pos[i]定義i號罪犯的編號。這裡其實是一種反向的思路，m點應該是最先釋放的（？Pos[r+1] - Pos[l-1] -2即此區間兩側最近的罪犯之間的人數，減去區間兩端。即區間合併的額外費用。注意要在Pos陣列中定義Pos[Q+1]=N+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <iostream>
#include <climits>
using namespace std;
int Pos[110];
int f[110][110];
int main() {
int P, Q;
cin >> P >> Q;
for(int i = 1; i<=Q; i++){
cin >> Pos[i];
}
Pos[Q+1] = P+1;
for(int k = 1; k<=Q; k++){
for(int i = 1; i+k-1<=Q; i++){
int y = i+k-1;
f[i][y]=INT_MAX;
for(int m = i; m<=y; m++){
f[i][y] = min(f[i][m-1] + f[m+1][y], f[i][y]);
}
f[i][y] += Pos[y+1] - Pos[i-1] -2;
}
}
cout << f[1][Q] << endl;
return 0;
}
本題難點在於建模，區間DP部分比較典型。