Hiểu bài toán

Bài toán yêu cầu chọn một tập hợp con các công việc từ danh sách n công việc để tối đa hóa tổng giá trị (tiền thu được). Mỗi công việc i có hai thông số: thời gian hoàn thành t (thời điểm phải nộp) và giá trị val. Tuy nhiên, có một ràng buộc về thời gian: để thực hiện một công việc tại thời điểm k (tức là công việc đó được chọn và có thời gian hoàn thành là k), cần phải có một công việc khác (hoặc không có công việc nào) đã được thực hiện tại thời điểm k-1. Hay cách khác, các công việc được chọn phải tạo thành một chuỗi liên tiếp về mặt thời gian bắt đầu từ 0. Cụ thể, nếu một công việc có thời gian t, ta cần đảm bảo rằng có thể đã thực hiện các công việc ở các mốc thời gian 0, 1, ..., t-1. Nếu không có công việc nào ở một mốc thời gian trước đó, ta không thể 'nhảy' tới một mốc thời gian lớn hơn. Mục tiêu là tìm tổng giá trị lớn nhất có thể và liệt kê các công việc được chọn.

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

Cách Quy hoạch động theo công việc và thời gian (Dynamic Programming)

#include <bits/stdc++.h>
#define tmax 10001
#define N 201
using namespace std;

struct work {
    int t, val, id;
};

work a[N];
int dp[N][tmax]; // dp[i][k]: tổng giá trị lớn nhất khi chọn công việc thứ i là công việc cuối cùng được nộp tại thời gian k
int n, res = 0;
int d[N]; // Mảng đánh dấu các công việc được chọn
vector<int> p;

bool cmp(work X, work Y) {
    // Sắp xếp theo thời gian tăng dần, nếu bằng thì giá trị giảm dần
    return (X.t < Y.t) || (X.t == Y.t && X.val > Y.val);
}

int main() {
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t >> a[i].val;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);

    int row, col;
    // Quy hoạch động
    for (int i = 1; i <= n; i++) {
        // Duyệt qua các thời gian giao nộp có thể của công việc i
        for (int k = 1; k <= a[i].t; k++) {
            // Duyệt qua các công việc trước đó j để tìm cách chuyển trạng thái
            for (int j = 0; j < i; j++) {
                dp[i][k] = max(dp[i][k], dp[j][k - 1] + a[i].val);
                if (res < dp[i][k]) {
                    res = dp[i][k];
                    row = i;
                    col = k;
                }
            }
        }
    }

    // Truy vết đường đi
    while (row > 0 && col > 0) {
        for (int i = row - 1; i >= 0; i--) {
            if (dp[row][col] == dp[i][col - 1] + a[row].val) {
                p.push_back(a[row].id);
                d[a[row].id] = 1;
                row = i;
                col--;
                break;
            }
        }
    }

    // In kết quả (đoạn code bị truncate trong mẫu nhưng logic là in ra tổng tiền và danh sách công việc)
    cout << res << endl;
    // ... logic in ra các công việc trong vector p ...
    return 0;
}

• Time Complexity: O(N * Tmax^2) hoặc O(N^2 * Tmax) tùy cách duyệt, trong code mẫu là O(N * Tmax * N) ~ O(N^2 * T). Với N=200, T=10000, phép tính này khá lớn (~2*10^8), nhưng có thể tối ưu.
• Space Complexity: O(N * Tmax)

Đây là cách tiếp cận trực tiếp từ bài toán gốc. Ta định nghĩa dp[i][k] là trạng thái khi công việc thứ i được chọn và là công việc cuối cùng được thực hiện tại thời điểm k. Để tính dp[i][k], ta duyệt qua tất cả các công việc j trước i (vì đã sắp xếp theo thời gian) và các mốc thời gian k-1. Công thức chuyển trạng thái là dp[i][k] = max(dp[j][k-1] + val[i]). Mảng dp được khởi tạo bằng 0. Sau khi tính toán xong, ta tìm giá trị lớn nhất trong mảng dp, đó là kết quả bài toán. Cuối cùng, ta truy vết lại các công việc đã dẫn đến trạng thái tối ưu đó.

Cách Tối ưu Quy hoạch động (Optimization)

// Ý tưởng tối ưu:
// Thay vì duyệt j từ 0 đến i-1 để tìm max(dp[j][k-1]), ta có thể sử dụng mảng phụ.
// Hoặc nhận thấy rằng:
// dp[i][k] = max(dp[j][k-1]) + val[i] (với j < i và dp[j][k-1] > 0)
// Nếu ta duy trì một mảng maxDP[k] lưu giá trị dp lớn nhất cho thời gian k,
// nhưng phải xét điều kiện công việc j phải có thời gian t >= k-1 (sau khi sort).

// Tuy nhiên, với ràng buộc 'liên tiếp về thời gian', một cách tiếp cận khác là:
// Gom nhóm các công việc theo thời gian.
// dp[time][i] là max value tại thời điểm time với công việc cuối cùng là i.
// Hoặc chỉ cần dp[time] là max value tại thời điểm time.
// Nhưng phải đảm bảo công việc tại time có t >= time.

// Code tối ưu (pseudo-code):
vector<int> jobs_at_time[Tmax];
// Gom nhóm job vào các mốc thời gian tương ứng
// Sau đó duyệt time từ 1 đến Tmax:
//   max_prev = dp[time-1]; (hoặc max của dp[time-1] qua các job)
//   Nếu max_prev == -1 (không thể reaching time-1) thì skip time này.
//   Duyệt các job tại time:
//     dp[time] = max(dp[time], max_prev + job.val)

// Tuy nhiên, bài toán này có twist: các công việc có thể có thời gian t chẵn/lẻ,
// và việc 'nhảy' thời gian bị cấm. Giải pháp Quy hoạch động 3 vòng lặp là an toàn nhất cho N nhỏ.

• Time Complexity: Có thể giảm xuống O(N * T) nếu tối ưu vòng lặp j bằng cách pre-calculate prefix max.
• Space Complexity: O(N * T)

Trong solution 1 và 2, vòng lặp for(int j=0; j<i; j++) là điểm nghẽn. Ta có thể tối ưu bằng cách duy trì một mảng maxVal[t] lưu giá trị dp lớn nhất tại thời điểm t của bất kỳ công việc nào đã xét. Tuy nhiên, do tính chất 'liên tiếp' (phải đi qua k-1 để đến k), ta có thể sắp xếp các công việc theo thời gian và duyệt theo từng mốc thời gian. Nếu công việc có thời gian t, nó chỉ có thể được thực hiện nếu dp[t-1] có giá trị > 0 (tức là có đường đi đến t-1). Cấu trúc dp[i][k] có thể được gộp lại thành dp[k] là giá trị lớn nhất có thể đạt được tại thời điểm k.

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

Bài học kinh nghiệm

• Vấn đề có thể được mô hình hóa như một bài toán tìm đường đi trên đồ thị có trọng số, nơi các node là các mốc thời gian (hoặc các công việc) và cạnh nối từ công việc j sang i nếu t(i) > t(j) (và thỏa mãn ràng buộc thời gian).
• Việc sắp xếp các công việc theo thời gian tăng dần là bước tiền xử lý quan trọng để đảm bảo khi duyệt công việc i, ta chỉ cần xét các công việc j trước đó (j < i) đã được xử lý.
• Ràng buộc 'phải đi qua thời gian k-1 để đến k' có nghĩa là nếu không có công việc nào được chọn tại thời gian k-1, ta không thể chọn công việc tại thời gian k (trừ khi k=0 hoặc k=1).

Lỗi thường gặp

• Không xử lý đúng trường hợp các công việc có cùng thời gian: Nếu hai công việc có cùng t, ta chỉ có thể chọn một trong hai (hoặc cả hai nếu t cho phép, nhưng logic bài toán thường chỉ chọn 1). Việc sort giảm dần giá trị giúp ưu tiên chọn công việc giá trị cao hơn nếu cùng thời điểm.
• Lỗi truy vết (backtracking): Khi truy vết, cần đảm bảo tìm được đúng công việc j trước đó đã tạo ra dp[i][k]. Việc duyệt từ i-1 về 0 trong code mẫu là cách làm an toàn.
• Vấn đề về giới hạn mảng: Mảng dp được định nghĩa kích thước tmax = 10001. Nếu t của công việc lớn hơn 10000, cần xử lý (vì trong bài này t có vẻ nhỏ).