Hiểu bài toán

Bài toán yêu cầu tìm tổng hạnh phúc lớn nhất mà Kaninho có thể đạt được trong N ngày nghỉ hè. Mỗi ngày, anh ấy chọn một trong ba hoạt động (A, B, C) với giá trị hạnh phúc tương ứng là ai, bi, c_i. Ràng buộc quan trọng là Kaninho không thể thực hiện cùng một hoạt động trong hai ngày liên tiếp. Ta cần tìm một chuỗi các quyết định (mỗi ngày chọn một hoạt động) thỏa mãn ràng buộc và có tổng hạnh phúc lớn nhất.

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

Cách Quy hoạch động (Dynamic Programming)

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100001];
int b[100001];
int c[100001];
long long dp[100001][4]; // dp[i][1]: tổng HH lớn nhất đến ngày i và chọn A

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];

    dp[1][1] = a[1];
    dp[1][2] = b[1];
    dp[1][3] = c[1];

    for (int i = 2; i <= n; i++){
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + a[i];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][3]) + b[i];
        dp[i][3] = max(dp[i - 1][1], dp[i - 1][2]) + c[i];
    }
    cout << max({dp[n][1], dp[n][2], dp[n][3]});
    return 0;
}

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

Đây là cách tiếp cận chuẩn sử dụng Quy hoạch động (DP).

1. Định nghĩa trạng thái: dp[i][j] là tổng hạnh phúc lớn nhất có thể đạt được sau i ngày, trong đó ngày thứ i chọn hoạt động j (1: A, 2: B, 3: C).
2. Cơ sở: Với ngày đầu tiên (i=1), dp[1][j] đơn giản là giá trị hạnh phúc của hoạt động đó.
3. Công thức chuyển trạng thái: Để tính dp[i][j], ta xét các giá trị của ngày trước đó (i-1). Vì không được chọn hoạt động giống nhau liên tiếp, ta chỉ được lấy giá trị lớn nhất từ các hoạt động khác của ngày trước cộng với giá trị của hoạt động hiện tại.
   • dp[i][1] = max(dp[i-1][2], dp[i-1][3]) + a[i]
   • dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + b[i]
   • dp[i][3] = max(dp[i-1][1], dp[i-1][2]) + c[i]
4. Kết quả: Giá trị lớn nhất trong dp[n][1], dp[n][2], dp[n][3] là đáp án.

Cách Quy hoạch động tối ưu bộ nhớ

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct acest
{
   ll a,b,c;
};
acest f[100005];
void ace()
{
   ll n;
      cin >> n;
   for(int i = 1; i <= n; i++)
      cin >> f[i].a >> f[i].b >> f[i].c;
   for(int i = 2; i <= n ;i++)
   {
      f[i].a += max(f[i-1].b , f[i-1].c);
      f[i].b += max(f[i-1].a , f[i-1].c);
      f[i].c += max(f[i-1].a , f[i-1].b);
   }
   ll t1 = max(f[n].a, f[n].b);
   cout << max(t1, f[n].c);
}
int main()
{
   ace();
}

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

Cách tiếp cận này giống về logic với DP chuẩn nhưng tối ưu việc khai báo mảng.

• Thay vì dùng mảng 2 chiều dp[N][3], ta dùng 1 mảng các cấu trúc (struct) hoặc 3 mảng 1 chiều.
• Logic tính toán giữ nguyên: Trạng thái hiện tại tại vị trí i được tính bằng cách lấy giá trị tại i cộng với giá trị lớn nhất hợp lệ từ i-1.
• Code ghi đè trực tiếp lên mảng dữ liệu của ngày hiện tại (sau khi đã lưu các giá trị của ngày trước vào biến tạm hoặc tính toán dựa trên vùng nhớ đã được cập nhật an toàn - trong code này, do cách tính tuần tự, f[i-1] đã chứa giá trị DP tối ưu của ngày trước, nên việc truy cập là chính xác).
• Đây là biến thể phổ biến trong thi đấu để viết code ngắn và dễ quản lý.

Cách Tối ưu bộ nhớ O(1)

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

int main() {
    int n;
    cin >> n;
    long long a, b, c;
    cin >> a >> b >> c;
    for (int i = 2; i <= n; i++) {
        long long na, nb, nc;
        long long x, y, z;
        cin >> x >> y >> z;
        na = max(b, c) + x;
        nb = max(a, c) + y;
        nc = max(a, b) + z;
        a = na; b = nb; c = nc;
    }
    cout << max({a, b, c});
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là phiên bản tối ưu nhất.

• Ta nhận thấy để tính giá trị cho ngày i, ta chỉ cần giá trị của ngày i-1.
• Do đó, thay vì lưu trữ toàn bộ quá khứ, ta chỉ cần 3 biến (hoặc 6 biến nếu dùng biến tạm) để lưu 3 giá trị DP của ngày trước.
• Vòng lặp đọc dữ liệu và cập nhật DP diễn ra song song.
• new_A = max(old_B, old_C) + current_A.
• Bộ nhớ sử dụng là hằng số O(1), rất phù hợp với N lớn (dù N=10^5 không yêu cầu quá khắt khe về bộ nhớ, nhưng đây là practice tốt).

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 từng bước' và phụ thuộc vào quyết định ngay trước đó, đây là dấu hiệu của Quy hoạch động 1 chiều.
• Ràng buộc 'không được chọn cùng hoạt động 2 ngày liên tiếp' có thể được xử lý bằng cách chỉ truy cập các trạng thái khác trong công thức chuyển trạng thái.
• Vì N nhỏ (10^5) và không có ràng buộc phức tạp thêm, giải pháp O(N) là tối ưu.

Lỗi thường gặp

• Lỗi truy cập chỉ số mảng: Trong C++ mảng bắt đầu từ 0, nhưng nhiều người quen dùng từ 1, cần chú ý khi khai báo và nhập dữ liệu.
• Lỗi kiểu dữ liệu: Tổng hạnh phúc có thể lên tới 10^5 * 10^4 = 10^9, cần dùng long long (hoặc int64_t) để tránh tràn số nguyên.
• Lỗi logic DP: Confusion giữa việc cộng thêm giá trị mới và ghi đè trạng thái. Ví dụ: dp[i][A] phải cộng với a[i], không phải ghi đè bằng giá trị từ ngày trước.