Hướng dẫn giải của Đoàn thanh tra

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hohoanghai5042011, lephuochauhungvuong, congtyluuthaibao1978

Editorial for travelab: Đoàn thanh tra

Hiểu bài toán

Bài toán chia dãy số từ 1 đến n thành 2 dãy con tăng dần (mỗi số thuộc đúng 1 dãy) sao cho tổng quãng đường di chuyển giữa các phần tử liên tiếp trong cả 2 dãy là nhỏ nhất. Quãng đường từ công ty s đến t là một hằng số đã cho (ma trận kề), không nhất thiết thỏa mãn tính chất khoảng cách. Điều này có nghĩa là ta chỉ quan tâm đến chi phí di chuyển giữa các công ty theo thứ tự phân công, và chi phí này phụ thuộc vào công ty hiện tại và công ty tiếp theo, chứ không phụ thuộc vào toàn bộ lịch sử di chuyển. Hai thanh tra có thể bắt đầu mà không tốn chi phí (từ 'vô hình').

Hai dãy con phải thỏa mãn:

  1. Gồm các số 1, 2, ..., n.
  2. Mỗi số xuất hiện đúng 1 lần.
  3. Trong mỗi dãy, các số tăng dần.

Mục tiêu: Minimize tổng chi phí. Dạng bài toán: Dynamic Programming trên các cặp trạng thái.

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

Cách Quy hoạch động Dynamic Programming (Standard)
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n;
int d[1005][1005];
int dp[1005][1005]; // dp[i][j]: chi phí nhỏ nhất khi A đã kiểm tra xong i, B đã kiểm tra xong j (i hoặc j có thể là 0)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> d[i][j];
        }
    }

    // Khởi tạo
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;

    // Duyệt theo thứ tự công ty được giao
    // k là công ty lớn nhất đã được giao cho 1 trong 2 người
    for (int k = 0; k < n; k++) {
        for (int i = 0; i <= k; i++) {
            int j = k; // Hoặc j = i, nhưng ta cần duyệt đủ các cặp (i, j) mà max(i, j) = k
            // Thực ra ta cần duyệt i từ 0 đến k, j từ 0 đến k sao cho max(i, j) == k
            // Hoặc đơn giản hơn: duyệt dp[i][j] và cập nhật cho công ty k+1
        }
    }

    // Cập nhật lại vòng lặp chính xác theo Solution 1:
    // Duyệt k là công ty hiện tại (max(i, j))
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i <= k; ++i) {
            int j = k;
            // Nếu dp[i][j] hợp lệ
            if (dp[i][j] < INF) {
                int next = k + 1;
                // Trả tiếp cho A
                // Nếu A chưa đi đâu (i == 0), chi phí từ 0 -> next là 0
                // Nếu A đã ở i, chi phí từ i -> next là d[i][next]
                int costA = (i == 0) ? 0 : d[i][next];
                dp[next][j] = min(dp[next][j], dp[i][j] + costA);
            }

            // Tương tự cho j
            if (dp[j][i] < INF) { // Symmetry: state (j, i)
                 int next = k + 1;
                 int costB = (i == 0) ? 0 : d[i][next];
                 dp[j][next] = min(dp[j][next], dp[j][i] + costB);
            }
        }
    }

    // ... (phần còn lại của code để lấy kết quả)
    return 0;
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)

Sử dụng mảng 2 chiều dp[i][j] để lưu trạng thái.

  • Trạng thái (i, j): Thanh tra A vừa kiểm tra xong công ty i, thanh tra B vừa kiểm tra xong công ty i.
  • Công ty k tiếp theo (bằng max(i, j) + 1) sẽ được giao cho A hoặc B.
  • Nếu giao cho A: Chi phí mới = dp[i][j] + d[i][k+1]. Trạng thái mới là (k+1, j).
  • Nếu giao cho B: Chi phí mới = dp[i][j] + d[j][k+1]. Trạng thái mới là (i, k+1).
  • Khởi tạo dp[0][0] = 0. Các vị trí khác là vô cùng.
  • Kết quả là min(dp[n][i] + ...) nhưng thực ra chỉ cần duyệt qua các state cuối cùng.
  • Lưu ý: d[i][j] là chi phí từ i đến j. Nếu i=0 (chưa đi đâu), chi phí là 0.
Cách Quy hoạch động Optimization (Compact)
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n;
int d[1005][1005];
int dp[1005][1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> d[i][j];

    // Khởi tạo
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;

    // Duyệt qua các công ty k từ 1 đến n
    // Với mỗi công ty k, ta cập nhật các state liên quan
    // State (i, j) có max(i, j) < k
    // Khi xử lý công ty k, ta thực chất đang mở rộng từ các state cũ

    // Solution 2 & 3 sử dụng vòng lặp lồng nhau:
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (dp[i][j] == INF) continue;
            int k = max(i, j) + 1;
            if (k > n) continue;

            // A nhận công ty k
            // Nếu A chưa đi (i=0), chi phí từ A đến k là 0
            // Nếu A đã ở i, chi phí là d[i][k]
            int costA = (i == 0) ? 0 : d[i][k];
            dp[k][j] = min(dp[k][j], dp[i][j] + costA);

            // B nhận công ty k
            int costB = (j == 0) ? 0 : d[j][k];
            dp[i][k] = min(dp[i][k], dp[i][j] + costB);
        }
    }

    int ans = INF;
    for (int i = 0; i <= n; i++) {
        ans = min(ans, dp[n][i]);
        ans = min(ans, dp[i][n]);
    }
    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)

Đây là cách tiếp cận trực quan hơn. Thay vì duyệt theo từng step của công ty k (max(i, j)), ta duyệt qua tất cả các state (i, j) có sẵn và thử giao công ty tiếp theo k = max(i, j) + 1 cho A hoặc B.

Logic:

  1. Vòng lặp for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) duyệt qua các state.
  2. Nếu dp[i][j] chưa được cập nhật (INF) thì bỏ qua.
  3. Tính k = max(i, j) + 1. Nếu k > n thì không còn công ty nào để giao.
  4. Cập nhật state mới:
    • Giao cho A: State (k, j). Chi phí cộng thêm: d[i][k] (hoặc 0 nếu i==0).
    • Giao cho B: State (i, k). Chi phí cộng thêm: d[j][k] (hoặc 0 nếu j==0).
  5. Kết quả cuối cùng là giá trị nhỏ nhất trong các state mà một trong hai chỉ số là n (tức là đã giao hết công ty).
Cách Giải thích chi tiết từ Code mẫu
// Tham khảo chi tiết từ Solution 1 (congtyluuthaibao1978)
// Logic tương tự Optimization nhưng cấu trúc vòng lặp khác

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int d[1005][1005];
int dp[1005][1005];

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> d[i][j];

    // Init
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;

    // Vòng lặp: k là công ty lớn nhất đã được giao
    for (int k = 0; k < n; k++) {
        // Duyệt tất cả các state mà max(i, j) == k
        for (int i = 0; i <= k; i++) {
            int j = k;
            // Xử lý state (i, j)
            // Solution 1 chỉ xét j = k, nhưng thực tế state (i, j) và (j, i) đều cần
            // Tuy nhiên, dữ liệu input không đối xứng, nhưng bài toán có tính chất
            // 'ai đi đường nấy'.
            // Code mẫu bị truncate, nhưng logic là:
            // Nếu dp[i][j] hợp lệ, cập nhật cho công ty k+1.

            if (dp[i][j] < INF) {
                int next = k + 1;
                // A làm next
                dp[next][j] = min(dp[next][j], dp[i][j] + (i == 0 ? 0 : d[i][next]));
                // B làm next
                dp[i][next] = min(dp[i][next], dp[i][j] + (j == 0 ? 0 : d[j][next]));
            }
        }
        // Cần xử lý thêm state (k, i) với i < k? 
        // Code mẫu bị thiếu phần này hoặc viết sai logic vòng lặp.
        // Solution 2 & 3 là chuẩn hóa tốt hơn.
    }

    int ans = INF;
    for (int i = 0; i <= n; i++) {
        ans = min(ans, dp[n][i]);
        ans = min(ans, dp[i][n]);
    }
    cout << ans;
    return 0;
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)

Phân tích chi tiết thuật toán trong code mẫu. Code mẫu ban đầu (Solution 1) có vẻ chỉ duyệt một nửa của không gian state (chỉ xét j = k trong khi i thay đổi), dẫn đến sai sót nếu không xử lý đối xứng. Tuy nhiên, Solution 2 và 3 đã sửa lại bằng cách duyệt toàn bộ không gian state (i, j) và tính k = max(i, j) + 1.

Các bước:

  1. Khởi tạo dp.
  2. Duyệt k từ 0 đến n-1.
  3. Duyệt i từ 0 đến k.
  4. Xét state (i, k) và (k, i) (cần kiểm tra cả 2).
    • Từ (i, k): Giao k+1 cho A (điều kiện i là người trước đó) hoặc B.
    • Tuy nhiên, logic j = k trong vòng lặp i chỉ xử lý được state mà người thứ hai là người cuối cùng.
    • Để xử lý full, nên dùng Solution 2 (Optimization).

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

Cách tiếp cận Time Space Tên
1 O(n^2) O(n^2) Quy hoạch động Dynamic Programming (Standard)
2 O(n^2) O(n^2) Quy hoạch động Optimization (Compact)
3 O(n^2) O(n^2) Giải thích chi tiết từ Code mẫu

Bài học kinh nghiệm

  • Bài toán có thể chia nhỏ thành các quyết định phân công công ty theo thứ tự từ 1 đến n.
  • Trạng thái chỉ cần quan tâm đến công ty cuối cùng mà mỗi người đã thăm (hoặc chưa thăm).
  • Chi phí di chuyển phụ thuộc vào công ty hiện tại và công ty tiếp theo ($d[i][k]$).
  • Vì các dãy phải tăng dần, ta duyệt công ty $k$ từ 1 đến $n$ và gán nó cho A hoặc B.

Lỗi thường gặp

  • Quên xử lý trường hợp một người chưa đi đâu (state 0). Khi đó chi phí di chuyển ban đầu là 0.
  • Sai lệch trong việc cập nhật state: Nếu chỉ duyệt một nửa không gian state (ví dụ chỉ xét j=k mà bỏ qua i=k với i<j), ta có thể bị thiếu state.
  • Giá trị INF quá nhỏ: Với $n=1000$, tổng chi phí có thể lên tới $10^6$ (nếu mỗi bước ~1000), nhưng 1e9 là đủ an toàn.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.