Bribe the Prisoners(GCJ 2009 Round 1C)

#Bribe the Prisoners(GCJ 2009 Round 1C)

DP。

像無界背包問題一樣，引入區間性質。

position[] 記錄囚犯的位置。 (a, b) 為開區間。 dp(a, b) 為釋放第 a+1 個 到第 b-1 個 囚犯所需的最少金幣，則

dp(a, b) 
= min([dp(a, c) + dp(c, b) for all c such that a < c < b]) + 		  
  cost to release current prisoner(c)

where cost to release current prisoner(c)
= (position[b]-1) - (position[a]+1) + 1 - 1

DP 的初使條件，因 (a, b) 是開區間，所以

dp(i, i+1) = 0

為實作方便，另外假設有兩個囚犯分別在通道的頭跟尾。

position[0] = 0;
position[Q+1] = P+1;

結果便是：

dp(0, Q+1)

Code

採 Top-down 的方式來建 dp。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

int dp[100+2][100+2];
int pos[100+2];

int solve(int left, int right) {
    if (dp[left][right] != -1)
        return dp[left][right];

    if (left + 1 == right)
        return dp[left][right] = 0;

    dp[left][right] = 10000000;
    for (int c = left+1; c < right; c++) {
        int value = solve(left, c) + solve(c, right) +
                    (pos[right]-1) - (pos[left]+1) +1 -1;
        dp[left][right] = min(dp[left][right], value);
    }

    return dp[left][right];
}

int main() {
    int N;
    cin >> N;

    for (int case_ = 1; case_ <= N; case_++) {
        memset(dp, -1, sizeof(dp));
        memset(pos, -1, sizeof(pos));

        int P, Q;
        cin >> P >> Q;

        pos[0] = 0;
        for (int i=1; i<=Q; i++)
            cin >> pos[i];
        pos[Q+1] = P+1;

        cout << "Case #" << case_ << ": " << solve(0, Q+1) << endl;
    }

    return 0;
}

amoshyc/bribe_the_prisoner.md

Code