Phân tích

Bài toán này được giải bằng phương pháp quy hoạch động. Với mỗi cặp phòng \(a \le b\), chúng ta muốn tính dp[a][b], là kết quả tốt nhất nếu chúng ta chỉ có các tù nhân trong các phòng từ \(a\) đến \(b\), bao gồm cả hai đầu. Khi chúng ta quyết định vị trí \(c\) là tù nhân đầu tiên trong khoảng từ \(a\) đến \(b\) được thả, chúng ta sẽ đối mặt với các bài toán con nhỏ hơn là dp[a][c-1] và dp[c+1][b]. Câu trả lời cuối cùng chúng ta muốn tìm là dp[1][P].

Rõ ràng là chúng ta chỉ cần giải các bài toán dp[a][b] mà ở đó cả \(a\) và \(b\) đều là 1, \(P\), hoặc nằm cạnh một tù nhân sẽ được thả. Do đó, số lượng bài toán con chúng ta cần giải chỉ là \(O(Q^2)\).

Cách cài đặt

Dưới đây là lời giải có chú thích của giám khảo.

int p[200]; // prisoners to be released.
map<pair<int, int>, int> dp;

// Finds the minimum amount of gold needed, 
// if we only consider the cells from a to b, inclusive.
int Solve(int a, int b) {
  // First, look up the cache to see if the 
  // result is computed before.
  pair<int, int> pr(a, b);
  if(mp.find(pr) != mp.end()) return mp[pr];

  // Start the computation.  
  int r = 0;
  for(int i=0; i<Q; i++) {
    if(p[i] >= a && p[i] <= b) {
      int tmp = (b-a) + Solve(a, p[i]-1) + Solve(p[i]+1, b);
      if (!r || tmp<r) r=tmp;
    }
  }
  mp[pr]=r;
  return r;
}

Độ phức tạp

• Số lượng trạng thái quy hoạch động là \(O(Q^2)\).
• Với mỗi trạng thái, chúng ta duyệt qua tối đa \(Q\) lựa chọn cho tù nhân được thả đầu tiên.
• Tổng độ phức tạp thời gian là \(O(Q^3)\) cho mỗi bộ test.
• Với \(Q \le 100\), thuật toán này hoạt động hiệu quả trong giới hạn thời gian cho phép.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 1C - Bribe the Prisoners, thuộc kho Google Coding Competitions (Apache-2.0).