Phân tích mô hình và ràng buộc

Hệ thống quản lý một hàng đợi gồm n đối tượng, mỗi đối tượng i mang một hệ số chờ đợi Di. Khi một đối tượng là người thứ k được xử lý, chi phí không hài lòng sinh ra là (k - 1) * Di. Để điều chỉnh thứ tự xử lý, hệ thống hỗ trợ một bộ nhớ đệm hoạt động theo cơ chế ngăn xếp (LIFO). Nhiệm vụ là tìm cách luân chuyển các đối tượng qua bộ nhớ đệm sao cho tổng chi phí của toàn bộ n đối tượng đạt giá trị nhỏ nhất.

Dữ liệu đầu vào bao gồm số lượng test case T, kích thước hàng đợi n (với 1 ≤ n ≤ 100) và dãy hệ số Di (với 0 ≤ Di ≤ 100). Kết quả cần trả về giá trị tối thiểu cho mỗi test case.

Chiến lược quy hoạch động trên khoảng

Đặc tính LIFO của ngăn xếp cho phép chia nhỏ bài toán thành các bài toán con độc lập. Xét một đoạn con các đối tượng liên tiếp từ vị trí l đến r. Nếu đối tượng đứng đầu đoạn l được xử lý ở vị trí thứ k trong phạm vi đoạn này (l ≤ k ≤ r), thì:

• Nhóm đối tượng từ l + 1 đến k buộc phải vào ngăn xếp trước và sẽ ra trước đối tượng l.
• Nhóm đối tượng từ k + 1 đến r sẽ được xử lý sau khi đối tượng l rời đi.

Hai nhóm con này không can thiệp lẫn nhau về mặt cấu trúc ngăn xếp, cho phép áp dụng quy hoạch động. Đặt dp[l][r] là tổng chi phí tối thiểu để xử lý đoạn [l, r]. Sử dụng mảng tổng tiền tố P[x] = Σ Di để tính nhanh tổng hệ số của các đoạn con.

Công thức chuyển trạng thái khi cố định vị trí ra của đối tượng l là k:

dp[l][r] = min(dp[l][r], (k - l) * D[l] + dp[l + 1][k] + dp[k + 1][r] + (k - l + 1) * (P[r] - P[k]))

Trong đó:

• (k - l) * D[l]: Chi phí chờ của đối tượng l.
• dp[l + 1][k]: Chi phí tối ưu của nhóm xử lý trước.
• dp[k + 1][r]: Chi phí tối ưu của nhóm xử lý sau.
• (k - l + 1) * (P[r] - P[k]): Hệ số trễ cộng thêm cho nhóm sau do phải chờ k - l + 1 đối tượng phía trước.

Khởi tạo dp[i][i] = 0 và các trạng thái không hợp lệ bằng giá trị vô cùng lớn. Duyệt theo độ dài đoạn con từ 2 đến n để đảm bảo tính đúng đắn của truy hồi.

Triển khai thuật toán

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

constexpr int MAX_SIZE = 105;
constexpr int INF_VAL = 1e9;

int dissatisfaction[MAX_SIZE];
int prefix_acc[MAX_SIZE];
int min_cost[MAX_SIZE][MAX_SIZE];

void process_test_case(int case_idx) {
    int total;
    cin >> total;
    
    prefix_acc[0] = 0;
    for (int idx = 1; idx <= total; ++idx) {
        cin >> dissatisfaction[idx];
        prefix_acc[idx] = prefix_acc[idx - 1] + dissatisfaction[idx];
    }

    for (int i = 1; i <= total + 1; ++i) {
        for (int j = 0; j <= total; ++j) {
            min_cost[i][j] = (i > j) ? 0 : INF_VAL;
        }
    }

    for (int span = 2; span <= total; ++span) {
        for (int left = 1; left <= total - span + 1; ++left) {
            int right = left + span - 1;
            for (int pos = left; pos <= right; ++pos) {
                int wait_penalty = (pos - left) * dissatisfaction[left];
                int left_group = min_cost[left + 1][pos];
                int right_group = min_cost[pos + 1][right];
                int delay_factor = (pos - left + 1) * (prefix_acc[right] - prefix_acc[pos]);
                
                min_cost[left][right] = min(min_cost[left][right], 
                                          wait_penalty + left_group + right_group + delay_factor);
            }
        }
    }

    cout << "Case #" << case_idx << ": " << min_cost[1][total] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    if (cin >> test_cases) {
        for (int t = 1; t <= test_cases; ++t) {
            process_test_case(t);
        }
    }
    return 0;
}