Problem
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window. All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.
The obvious way is to brute force all possible ordering of prisoners and compute the minimum gold coins spent. This works easily for the small case as there are only 5 prisoners awaiting to be released at the worst case. This obviously does not work for the large case as there can be as many as 100 prisoners to be released. To optimise this we turn to dynamic programming. Seeing there can be as many as 100 prisoners to be released we can't keep a bitmask of which prisoners we have released as it will certainly TLE and/or exceed memory limit (on all current systems). The key observation is to divide the prison into sub-prisons. This can be seen by noting that the ends of the prison cells act as barriers/walls in which the word does not go through. If we release prisoners from cells - the cells we have just freed implicitly acts like the ends of our original prison.
In addition, we need to make a small optimisation as the prisons can be as large as 10,000 in the large case. We need to note that we will never free from a cell which is not in the list of prisoners to be freed. Hence instead of keeping track of the index of the prison cells itself, we keep track of the index of the prisoners to be freed. A simple sort suffices to keep the implementation neat. Hence the space complexity is only O(Q*Q) and since Q is at most only 100 - this is pretty much nothing.
So we define the DP state as:
D(n,m) = the minimum number of gold spent to free prisoners between index n and m of the prisoners to be freed.
Our recurrence relation is then simply defined as:
D(n,m) = min { Cost(i) + D(n,i) + D(i,m) } where n < i < m. (free prisoner i)
D(n,m) = 0 if m - n < 2 (base case)
The base case is for situations where there are no prisoners to be freed between n and m. Cost(i) is defined as the cost to free prisoner index i given that the empty prison to the left is n and the empty prison to the right is m. This can be calculated in constant time as we know which locations index n and m corresponds to. There is a small trick for implementing this - we add explicit left and right barriers to our original prison to make it conform to our recursion. This way we don't need to handle for the original prison special case which would otherwise be unbounded.
http://jecvay.com/2014/07/gcj-2008-2009-luangao/
首先想到的是递归解决问题, 比如dfs(a, b), 枚举i, a < i < b, 然后 dfs(a, b) = dfs(a, i) + dfs(i, b) + cost[i] 之类的. 考虑到这样可能会有重复计算的地方, 那么可以用记忆化搜索.
书上的状态定义如下
dp[i][j] : 将从A[i]号到B[i]号的囚犯(不含这两个)的连续部分的所有囚犯都释放的时候, 所需要的最少金币总数.
显然”叶子节点”是 dp[i][i+1] = 0.
目标是要求出dp[0][Q+1].
从叶子节点向上延伸一层的时候, 就是状态转移方程要写出的意思:
dp[i][j] = A[j] – A[i] – 2 + min{dp[i][k], dp[k][j]} , i < k < j.
int memo[111][111]; vector<int> data; int func(int leftIdx, int rightIdx) { // base case if (rightIdx - leftIdx < 2) { return 0; } if (memo[leftIdx][rightIdx] != -1) return memo[leftIdx][rightIdx]; int res = 1<<30; for (int i = leftIdx+1; i < rightIdx; i++) { // split on prisoner index i int calc = (data[i] - data[leftIdx] - 1) + (data[rightIdx] - data[i] - 1); calc = calc + func(leftIdx, i) + func(i, rightIdx); res = min(res,calc); } return memo[leftIdx][rightIdx] = res; } int main() { int N; cin >> N; for (int t = 0; t < N; t++) { int P, Q; cin >> P >> Q; vector<int> pris; for (int i = 0; i < Q; i++) { int val; cin >> val; pris.push_back(val); } // add explicit barriers to the ends of the prisons pris.push_back(0); pris.push_back(P+1); // ensure that the prisoner indexes are strictly increasing sort(pris.begin(),pris.end()); data = pris; memset(memo,-1,sizeof(memo)); int best = func(0, data.size()-1); cout << "Case #" << t+1 << ": " << best << "\n"; } return 0; }Read full article from Dashboard - Round 1C 2009 - Google Code Jam
