Hiểu bài toán

Bài toán yêu cầu tìm cách sắp xếp N vị khách vào N ghế để tối đa hóa tổng độ hài lòng. Quy tắc: Vị khách VIP (khách 1) vào đầu tiên và chọn bất kỳ ghế nào. Các khách tiếp theo (khách i, i > 1) ưu tiên ngồi đúng ghế của mình (ghế i). Nếu ghế i đã bị chiếm, họ được chọn một ghế trống bất kỳ.

Ta cần chọn ghế cho khách VIP và các ghế thay thế (nếu có) sao cho tổng độ hài lòng lớn nhất.

Quy trình phân tích:

1. Khách VIP (1) chọn ghế k.
2. Các khách sau đó (2 đến N) lần lượt vào. Nếu khách i vào mà ghế i còn trống, họ ngồi đó. Nếu ghế i đã bị chiếm (bởi VIP hoặc một khách nào đó đã chọn ghế này trước đó), họ sẽ chọn lại một ghế trống.

Đặc điểm quan trọng: Nếu VIP chọn ghế 1 (ghế của chính VIP), thì mọi người đều có ghế của mình và tổng hài lòng là tổng các phần tử đường chéo (Cii).

Nếu VIP chọn ghế k (k ≠ 1), thì:

• Ghế k bị chiếm.
• Khách k vào sau cùng (vì k > 1), nên khi khách k vào, ghế k đã bị VIP chiếm. Khách k sẽ chọn lại.
• Các khách từ 2 đến k-1 đều có ghế trống (vì VIP chỉ chiếm ghế k, và các khách 2 đến k-1 vào trước khách k nên không bị ảnh hưởng). Họ đều ngồi đúng ghế.
• Khách k vào, thấy ghế k bị chiếm, chọn lại.

Trường hợp VIP chọn ghế k:

• VIP ở ghế k, được điểm C[1][k].
• Các khách từ 2 đến k-1 ở đúng ghế, cộng điểm C[i][i].
• Khách k vào, không có ghế k, chọn lại.

Phân tích tiếp: Nếu VIP chọn ghế k, thì khi đến lượt khách k, các ghế trống là: Ghế 1 (của VIP, VIP đang ở k nên ghế 1 trống) và các ghế từ k+1 đến N (chưa ai dùng). Khách k sẽ chọn ghế nào?

• Nếu chọn ghế 1: Được C[k][1].
• Nếu chọn ghế j > k: Được C[k][j].

Tuy nhiên, có một sự thật: Nếu VIP chọn ghế k, thì sau khi VIP vào, các khách 2, 3, ..., k-1 vào đúng chỗ. Khi khách k vào, họ chọn ghế.

Nếu khách k chọn ghế 1:

• VIP: C[1][k]
• Khách k: C[k][1]
• Các khách còn lại (k+1 đến N): Ngồi đúng chỗ (vì ai cũng có ghế).
• Tổng: C[1][k] + C[k][1] + sum(C[i][i] for i=2 to k-1) + sum(C[i][i] for i=k+1 to N)
• = sum(C[i][i] for all i) - C[1][1] - C[k][k] + C[1][k] + C[k][1]

Nếu VIP chọn ghế k, và sau đó khách k chọn ghế j > k:

• VIP: C[1][k]
• Khách k: C[k][j]
• Ghế j bị chiếm.
• Khi khách j vào (j > k), họ thấy ghế j bị chiếm, họ chọn lại.
• Quá trình này có thể tạo ra một chuỗi.

Nhưng có một cách tiếp cận Dynamic Programming (DP) khác được các giải pháp sử dụng.

Giải pháp trong code: Code dùng DP với ý tưởng: dp[i] là giá trị lớn nhất của tổng độ hài lòng khi xét đến khách thứ i (và VIP đã chọn ghế i?), không phải.

Thực tế, giải pháp này xử lý bài toán "VIP chọn ghế" bằng cách xem xét các khả năng VIP chọn ghế của người khác.

Hãy xem xét kỹ thuật trong code:

• s[i] = s[i-1] + a[i][i]: Tính tổng các phần tử đường chéo.
• dp[1] = s[n]: Trường hợp VIP chọn ghế 1.
• Vòng lặp for (int i = 2; i <= n; ++i): Duyệt qua các ghế mà VIP có thể chọn (hoặc các trạng thái).
• dp[i] = max(dp[i], dp[j] - a[j][1] + a[j][i] - a[i][i] + a[i][1])

Công thức này dựa trên ý tưởng: Giả sử VIP chọn ghế i. Nếu VIP chọn ghế i (i > 1), thì:

• VIP được C[1][i].
• Ghế 1 bị bỏ trống.
• Các khách từ 2 đến i-1 vào đúng chỗ.
• Khách i vào, không có ghế i, phải chọn ghế.
• Nếu khách i chọn ghế 1 (ghế của VIP): Được C[i][1].
• Sau đó các khách i+1 đến N đều có ghế.
• Tổng = (Tổng C[k][k] cho k=2..N) - C[i][i] + C[1][i] + C[i][1]
• = s[n] - a[i][i] + a[1][i] + a[i][1] - a[1][1] (vì s[n] bao gồm a[1][1] nhưng nếu VIP chọn i thì a[1][1] không được dùng).

Tuy nhiên, công thức dp[i] = dp[j] - a[j][1] + a[j][i] - a[i][i] + a[i][1] gợi ý về một chuỗi.

Chuỗi bù trừ (Cycle): Nếu VIP chọn ghế i, và i chọn ghế j, j chọn ghế k... cuối cùng quay lại ghế 1.

Hãy xét một chuỗi các chỉ số: 1, i1, i2, ..., im. VIP (1) chọn i1. Khách i1 chọn i2. ... Khách i_m chọn 1.

Tổng điểm:

• C[1][i_1]
• C[i1][i2]
• ...
• C[i_m][1]
• Các khách còn lại (không nằm trong chuỗi): C[k][k].

Tổng = sum(C[k][k] cho k không trong chuỗi) + sum(C[x][y] trong chuỗi).

Công thức dp[i] = dp[j] - a[j][1] + a[j][i] - a[i][i] + a[i][1] có vẻ như đang tính một "chu kỳ".

Giả sử dp[j] là tổng lớn nhất khi có một chu kỳ kết thúc tại j (tức là khách j chọn ghế 1). Khi thêm i vào chu kỳ:

• Thay vì j chọn 1 (điểm a[j][1]), j chọn i (điểm a[j][i]).
• Thêm i vào chu kỳ: i chọn 1 (điểm a[i][1]).
• i không còn ngồi đúng ghế (mất a[i][i]).

Vậy công thức là: dp[i] = dp[j] - a[j][1] + a[j][i] + a[i][1] - a[i][i]

Điều này đúng với logic:

• dp[j] là tổng khi có một chu kỳ kết thúc tại j.
• Nếu ta insert i vào trước j (tức là ... -> i -> j -> ... -> 1):
  • j trước đó chọn 1 (điểm a[j][1]), nay chọn i (điểm a[j][i]).
  • i được thêm vào, chọn 1 (điểm a[i][1]).
  • i không ngồi đúng ghế, mất a[i][i].

Vậy bài toán quy hoạch động này tìm "chu kỳ tốt nhất".

Tóm tắt:

1. Tính tổng cơ bản nếu ai cũng ngồi đúng chỗ: S = sum(C[i][i]).
2. Nếu VIP chọn ghế k, và mọi người đều có chỗ (trừ việc hoán đổi 1 và k), ta được S - C[1][1] - C[k][k] + C[1][k] + C[k][1].
3. Có thể có các "chu kỳ" lớn hơn involving nhiều người.
4. DP dp[i] tìm tổng lớn nhất khi xét các chu kỳ kết thúc tại i (tức i chọn 1).

Code thực hiện:

• dp[1] = s[n] (Trường hợp không có chu kỳ, VIP ở 1).
• Duyệt i từ 2 đến N.
• Với mỗi i, thử mọi j < i để tạo chu kỳ.
• dp[i] là tổng lớn nhất khi i chọn 1 (và có thể có các chu kỳ khác).
• Cuối cùng in max dp[i] (vì dp[i] là tổng khi i chọn 1, kết thúc chu kỳ).

Ngoài ra, code còn in max(s[n], mx). s[n] là trường hợp VIP chọn ghế 1.

Chi tiết logic:

• dp[j] là tổng độ hài lòng lớn nhất của một cấu trúc mà trong đó có một chu kỳ kết thúc tại j (tức j chọn ghế 1).
• Khi ta muốn thêm i vào chu kỳ (tạo thành ... -> i -> j -> ... -> 1):
  • Trước đó: j chọn 1, i chọn đúng ghế i (tặng a[i][i]).
  • Sau khi thêm: j chọn i (trừ a[j][1], cộng a[j][i]), i chọn 1 (trừ a[i][i], cộng a[i][1]).
  • Thay đổi: + a[j][i] - a[j][1] + a[i][1] - a[i][i].

Vậy dp[i] = dp[j] + delta.

Tại sao chỉ xét j < i? Để tránh lặp và đảm bảo tính chất topological (giả sử các chỉ số được xử lý theo thứ tự).

Kết quả là giá trị lớn nhất của dp[i] cho mọi i (vì dp[i] là tổng khi i chọn 1, kết thúc chu kỳ).

Vậy, các bước:

1. Đọc ma trận C.
2. Tính tổng đường chéo S.
3. dp[1] = S.
4. Duyệt i từ 2 đến N:
   • dp[i] khởi tạo -inf.
   • Duyệt j từ 1 đến i-1:
     • dp[i] = max(dp[i], dp[j] - C[j][1] + C[j][i] - C[i][i] + C[i][1]).
5. Kết quả là max(S, max(dp[2..N])).

Kiểm tra sample: N=4. Ma trận: 2 6 8 6 5 0 6 7 8 0 1 9 2 7 2 4

S = 2 + 0 + 1 + 4 = 7.

dp[1] = 7.

i = 2: j = 1: dp[2] = dp[1] - C[1][1] + C[1][2] - C[2][2] + C[2][1] dp[2] = 7 - 2 + 6 - 0 + 5 = 16.

i = 3: j = 1: dp[3] = 7 - 2 + 8 - 1 + 5 = 17. j = 2: dp[3] = dp[2] - C[2][1] + C[2][3] - C[3][3] + C[3][1] dp[3] = 16 - 5 + 6 - 1 + 8 = 24.

i = 4: j = 1: dp[4] = 7 - 2 + 6 - 4 + 5 = 12. j = 2: dp[4] = 16 - 5 + 7 - 4 + 2 = 16. j = 3: dp[4] = 24 - 8 + 9 - 4 + 2 = 23.

Max(dp[i]) = 24. Max(S, 24) = 24. Kết quả đúng.

Vậy đây là phương pháp Dynamic Programming tìm "chu kỳ tối ưu".

Các cách tiếp cận

Cách Quy hoạch động Dynamic Programming (Chu kỳ tối ưu)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a[1001][1001], dp[1001], mx = LLONG_MIN, s[1001];

    // Đọc dữ liệu và tính tổng đường chéo ban đầu
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
        s[i] = s[i - 1] + a[i][i];
    }

    // dp[i] là độ hài lòng lớn nhất khi khách i chọn ghế 1 (kết thúc một chu kỳ)
    // Khởi tạo trường hợp cơ bản: không có chu kỳ nào, VIP ở ghế 1
    dp[1] = s[n];

    for (int i = 2; i <= n; ++i) {
        dp[i] = LLONG_MIN;
        // Thử tạo chu kỳ mới hoặc mở rộng chu kỳ cũ từ j sang i
        for (int j = 1; j < i; ++j) {
             // Công thức chuyển trạng thái:
             // Lấy giá trị từ dp[j] (chu kỳ kết thúc ở j)
             // Thay j chọn 1 bằng j chọn i: +a[j][i] - a[j][1]
             // Thêm i vào chu kỳ, i chọn 1: +a[i][1]
             // i không còn ngồi đúng ghế: -a[i][i]
             dp[i] = max(dp[i], dp[j] - a[j][1] + a[j][i] - a[i][i] + a[i][1]);
        }
        mx = max(mx, dp[i]);
    }

    // Kết quả là max(Trường hợp VIP ở 1, Trường hợp VIP chọn các ghế khác)
    cout << max(s[n], mx) << endl;
    return 0;
}

• Time Complexity: O(N^2)
• Space Complexity: O(N^2)

Phương pháp này dựa trên quan sát rằng nếu VIP chọn một ghế khác ghế của mình, có thể tạo ra một chu kỳ hoán đổi ghế giữa VIP và các khách khác.

• dp[i] lưu tổng độ hài lòng lớn nhất khi xét các khách từ 1 đến i và có một chu kỳ hoán đổi kết thúc tại i (tức là i chọn ghế 1).
• Để tính dp[i], ta xem xét tất cả các vị trí j < i mà từ đó ta có thể kéo dài chu kỳ đến i.
• Nếu dp[j] là tổng tốt nhất với chu kỳ kết thúc ở j, để chuyển sang chu kỳ kết thúc ở i, ta thay đổi:
  • Khách j chuyển từ chọn ghế 1 sang chọn ghế i (điểm thay đổi: a[j][i] - a[j][1]).
  • Khách i được thêm vào chu kỳ, chọn ghế 1 (điểm: a[i][1]).
  • Khách i không còn ngồi đúng ghế của mình (trừ đi a[i][i]).
• Công thức cập nhật: dp[i] = max(dp[j] + a[j][i] - a[j][1] + a[i][1] - a[i][i]).
• Kết quả cuối cùng là giá trị lớn nhất giữa trường hợp VIP chọn ghế 1 (tổng đường chéo) và các trường hợp tạo chu kỳ (max dp[i]).

Cách Giải thích chi tiết Logic Quy hoạch động

// Xem Approach 1

• Time Complexity: O(N^2)
• Space Complexity: O(N^2)

Đây là biến thể của Approach 1, giải thích sâu hơn về ý nghĩa các biến:

• sum_diag: Tổng C[i][i] cho mọi i. Đây là cơ sở nếu mọi người đều ngồi đúng chỗ.
• dp[i]: Mô tả trạng thái khi khách i là người cuối cùng trong chuỗi hoán đổi ghế và chọn ghế số 1.
• Khi ta có một chuỗi 1 -> i_1 -> i_2 -> ... -> i_k -> 1, tổng điểm sẽ bao gồm:
  • C[1][i_1]
  • C[i_1][i_2]
  • ...
  • C[i_k][1]
  • C[x][x] cho các x không nằm trong chuỗi.
• DP cho phép ta xây dựng chuỗi này từng bước một cách hiệu quả.

Cách Giải thích biến thể từ các bài tương tự (Cycle Cover)

// Logic tương tự Approach 1

• Time Complexity: O(N^2)
• Space Complexity: O(N^2)

Bài toán này có thể coi là tìm một "Cycle Cover" (tập hợp các chu trình) trên đồ thị có hướng đầy đủ (trừ self-loop) với trọng số là C[i][j], sao cho tổng trọng số lớn nhất và có đúng một chu trình bắt nguồn từ VIP (khách 1). Trong các giải pháp nộp, ý tưởng này được tối ưu hóa bằng DP O(N^2) như đã mô tả ở trên. Điểm mấu chốt là chỉ cần quan tâm đến chu trình duy nhất chứa VIP (vì các chu trình khác không chứa VIP sẽ không có người khởi tạo, hoặc VIP phải là người duy nhất không có ghế).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể biến thành bài toán tìm "chu kỳ tối ưu" chứa VIP. Nếu VIP chọn ghế 1, không có chu kỳ. Nếu VIP chọn ghế k, một chu kỳ được hình thành.
• Quy hoạch động dp[i] là chìa khóa: Nó cho phép ta xây dựng tổng độ hài lòng dựa trên việc mở rộng chu kỳ từ các vị trí trước đó.
• Công thức chuyển trạng thái dp[i] = dp[j] - C[j][1] + C[j][i] - C[i][i] + C[i][1] là cách hiệu quả để tính toán sự thay đổi khi thêm i vào chu kỳ.

Lỗi thường gặp

• Quên trừ đi C[i][i] khi khách i không còn ngồi đúng ghế của mình.
• Sai lệch trong việc tính toán các chỉ số (1-based indexing vs 0-based indexing trong code mẫu là 1-based).
• Không xử lý đúng trường hợp cơ bản là VIP chọn ghế 1 (tức là dp[1] hoặc tổng đường chéo).