題解 P1622 釋放囚犯

發表於 分類於 閱讀次數： Waline： 文章字數： 1.7k

題目連結

題面

題目描述

Caima 王國中有一個奇怪的監獄，這個監獄一共有 PP 個牢房，這些牢房一字排開，第 ii 個緊挨著第 i+1i+1 個（最後一個除外）。現在正好牢房是滿的。

上級下發了一個釋放名單，要求每天釋放名單上的一個人。這可把看守們嚇得不輕，因為看守們知道，現在牢房中的 PP 個人，可以相互之間傳話。如果某個人離開了，那麼原來和這個人能說上話的人，都會很氣憤，導致他們那天會一直大吼大叫，搞得看守很頭疼。如果給這些要發火的人吃上肉，他們就會安靜點。

輸入格式

第一行兩個整數 PP 和 QQ，QQ 表示釋放名單上的人數；

第二行 QQ 個整數，表示要釋放哪些人，保證按遞增的順序給出。

輸出格式

僅一行，表示最少要給多少人次送肉吃。

樣例 #1

樣例輸入 #1

1
2
20 3
3 6 14

樣例輸出 #1

1
35

提示

樣例說明 #1

先釋放 1414 號監獄中的罪犯，要給 11 到 1313 號監獄和 1515 到 2020 號監獄中的 1919 人送肉吃；再釋放 66 號監獄中的罪犯，要給 11 到 55 號監獄和 77 到 1313 號監獄中的 1212 人送肉吃；最後釋放 33 號監獄中的罪犯，要給 11 到 22 號監獄和 44 到 55 號監獄中的 44 人送肉吃。

資料規模與約定

  • 對於 50%50\% 的資料，1≤P≤1001 \le P \le 100，1≤Q≤51 \le Q \le 5；
  • 對於 100%100\% 的資料，1≤P≤1031 \le P \le 10^3，1≤Q≤1001 \le Q \le 100，Q≤PQ \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> // For INT_MAX

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; // 答案即把 1...Q 所有的罪犯全部釋放（合併）
    return 0;
}

小結

本題難點在於建模，區間DP部分比較典型。