Hiểu bài toán

Cho một đoạn nhạc gồm N ô nhịp, mỗi ô nhịp có 2 nốt nhạc (Ai, Bi). Cần chọn ra M ô nhịp tạo thành đoạn nhạc mới sao cho:

1. Ô nhịp đầu tiên (1) và cuối cùng (N) luôn được giữ lại.
2. Độ xấu của đoạn nhạc mới là nhỏ nhất. Độ xấu được tính bằng tổng平方 của sự chênh lệch giữa nốt thứ 2 của ô nhịp trước và nốt thứ 1 của ô nhịp sau cho tất cả các cặp ô nhịp liên tiếp trong đoạn nhạc mới. Nếu hai ô nhịp liên tiếp trong đoạn nhạc mới vốn là 2 ô nhịp kề nhau trong đoạn nhạc cũ, độ xấu bằng 0.

Tóm lại, ta cần tìm một dãy con gồm M phần tử tăng dần $1 = x1 < x2 < \dots < xM = N$ sao cho tổng $\sum{j=1}^{M-1} \text{cost}(xj, x{j+1})$ là nhỏ nhất, với $\text{cost}(i, j) = 0$ nếu $j = i+1$, và $(Bi - Aj)^2$ nếu $j > i+1$.

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

Cách Quy hoạch động cơ bản (Dùng mảng 3 chiều)

int dp[N][M][N]; // dp[i][j][k]: i là chỉ số xét tới, j là số lượng ô nhịp đã chọn, k là ô nhịp được chọn cuối cùng
// Cập nhật:
// dp[i+1][j+1][i+1] = min(dp[i+1][j+1][i+1], dp[i][j][k] + cost(k, i+1))
// dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])

• Time Complexity: O(N^3 * M) ~ O(N^4)
• Space Complexity: O(N^3 * M) ~ O(N^4)

Sử dụng quy hoạch động với trạng thái dp[i][j][k] thể hiện độ xấu nhỏ nhất khi xét đến ô nhịp thứ i, đã chọn j ô nhịp, và ô nhịp cuối cùng được chọn là k. Với mỗi trạng thái, ta có 2 lựa chọn: bỏ qua ô nhịp i hoặc chọn ô nhịp i (nếu j chưa đủ M). Phương pháp này đúng nhưng quá chậm và tốn bộ nhớ cho N lên tới 200.

Cách Quy hoạch động tối ưu 2 chiều

int f[205][205];
f[1][1] = 0;
for (int i = 2; i <= n; i++) {
    for (int j = 2; j <= m; j++) {
        f[i][j] = 1e9;
        for (int k = 1; k < i; k++) {
            int cost = (k == i - 1) ? 0 : (b[k] - a[i]) * (b[k] - a[i]);
            f[i][j] = min(f[i][j], f[k][j - 1] + cost);
        }
    }
}
cout << f[n][m];

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

Cải tiến từ phương pháp 3 chiều. Trạng thái f[i][j] là độ xấu nhỏ nhất của đoạn nhạc có độ dài j kết thúc tại ô nhịp thứ i. Để tính f[i][j], ta duyệt qua tất cả các ô nhịp k trước i (k < i) và thực hiện chuyển trạng thái: f[i][j] = min(f[k][j-1] + cost(k, i)). Điều kiện là ô nhịp 1 phải được chọn và ô nhịp N phải được chọn. Ta có thể khởi tạo f[1][1] = 0 và chỉ quan tâm đến kết quả f[n][m].

Cách Quy hoạch động tối ưu với đệ quy nhớ (Memoization)

int solve(int pos, int count) {
    if (count == m) return (pos == n) ? 0 : INF;
    if (pos > n) return INF;
    if (memo[pos][count] != -1) return memo[pos][count];

    int res = INF;
    // Chọn tiếp ô nhịp tiếp theo là next_pos
    for (int next_pos = pos + 1; next_pos <= n; next_pos++) {
        int cost = (next_pos == pos + 1) ? 0 : (b[pos] - a[next_pos]) * (b[pos] - a[next_pos]);
        // Số lượng ô nhịp còn lại phải đủ để đi từ next_pos đến n
        if (n - next_pos + 1 >= m - count) {
             res = min(res, cost + solve(next_pos, count + 1));
        }
    }
    return memo[pos][count] = res;
}
// Khởi tạo: memset(memo, -1, sizeof(memo));
// Gọi: solve(1, 1)

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

Đây là cách tiếp cận đệ quy có nhớ. Hàm solve(pos, count) tính độ xấu nhỏ nhất khi đang ở ô nhịp pos và đã chọn count ô nhịp. Ta duyệt qua tất cả các vị trí có thể chọn tiếp theo (next_pos). Việc kiểm tra n - next_pos + 1 >= m - count đảm bảo rằng ta không đi vào các nhánh vô ích (không đủ ô nhịp để hoàn thành). Tuy nhiên, với N=200, đệ quy có thể gây tràn stack hoặc overhead lớn, nên cách chuyển về quy hoạch động lặp (Approach 2) thường được ưu tiên hơn trong lập trình thi đấu.

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

Bài học kinh nghiệm

• Bài toán có tính chất tối ưu trên dãy con tăng dần, phù hợp với quy hoạch động.
• Độ xấu giữa 2 ô nhịp liên tiếp phụ thuộc vào ô nhịp trước đó (nốt thứ 2) và ô nhịp hiện tại (nốt thứ 1), không phụ thuộc vào các ô nhịp trước đó nữa. Do đó, bài toán có thể quy về bài toán tìm đường đi ngắn nhất trên đồ thị có hướng với các cạnh từ i đến j (i < j).
• Cần xử lý đặc biệt trường hợp j = i + 1 (ô nhịp kề nhau) để chi phí bằng 0.

Lỗi thường gặp

• Quên kiểm tra điều kiện ô nhịp đầu (1) và cuối (N) phải được chọn.
• Xử lý sai chi phí khi 2 ô nhịp kề nhau (phải là 0 thay vì tính theo công thức chung).
• Lặp quá sâu gây tràn stack trong cách tiếp cận đệ quy nếu không chuyển về dạng lặp.
• Bỏ qua các trường hợp không đủ ô nhịp để hoàn thành dãy độ dài M (cần prune nhánh trong đệ quy hoặc đảm bảo vòng lặp hợp lệ).