Hướng dẫn thuật toán

Link bài tập

1. Phân tích bài toán bằng ngôn ngữ tự nhiên

• Mục tiêu: Chọn hoạt động mỗi ngày để tổng điểm hạnh phúc là lớn nhất.
• Điều kiện ràng buộc: "Không thực hiện cùng một hoạt động trong hai ngày liên tiếp".
  • Nếu hôm nay chọn A, ngày mai chỉ được chọn B hoặc C.
  • Nếu hôm nay chọn B, ngày mai chỉ được chọn A hoặc C.
  • Nếu hôm nay chọn C, ngày mai chỉ được chọn A hoặc B.
• Nhận xét: Để quyết định ngày hôm nay nên làm gì, chúng ta không chỉ cần biết tổng điểm của những ngày trước, mà còn phải biết hôm qua đã làm việc gì.

2. Tư duy thuật toán (Quy hoạch động)

Chúng ta sẽ sử dụng một bảng (mảng 2 chiều) để lưu trữ kết quả. Gọi dp[i][j] là tổng điểm hạnh phúc tối đa tính đến hết ngày thứ i, với điều kiện vào ngày thứ i Taro thực hiện hoạt động j.

• j = 0: Hoạt động A (Bơi biển)
• j = 1: Hoạt động B (Bắt bọ)
• j = 2: Hoạt động C (Làm bài tập)

Công thức truy hồi:

Để tính điểm tối đa cho ngày i:

1. Nếu ngày i chọn A (dp[i][0]):
   • Ngày i-1 phải là B hoặc C.
   • dp[i][0] = a[i] + lớn_nhất(dp[i-1][1], dp[i-1][2])
2. Nếu ngày i chọn B (dp[i][1]):
   • Ngày i-1 phải là A hoặc C.
   • dp[i][1] = b[i] + lớn_nhất(dp[i-1][0], dp[i-1][2])
3. Nếu ngày i chọn C (dp[i][2]):
   • Ngày i-1 phải là A hoặc B.
   • dp[i][2] = c[i] + lớn_nhất(dp[i-1][0], dp[i-1][1])

Trạng thái cơ sở (Ngày 1):

• dp[1][0] = a[1]
• dp[1][1] = b[1]
• dp[1][2] = c[1]

3. Các bước thực hiện

1. Nhập dữ liệu: Đọc số ngày và danh sách điểm cho mỗi ngày.
2. Khởi tạo: Tạo mảng dp[N+1][3].
3. Thiết lập ngày đầu tiên: Gán giá trị hạnh phúc của ngày 1 vào dp[1][0], dp[1][1], dp[1][2].
4. Tính toán: Chạy vòng lặp từ ngày đến :
   • Tính dp[i][0] dựa trên kết quả ngày của cột 1 và 2.
   • Tính dp[i][1] dựa trên kết quả ngày của cột 0 và 2.
   • Tính dp[i][2] dựa trên kết quả ngày của cột 0 và 1.
5. Kết quả: Giá trị lớn nhất trong 3 giá trị dp[N][0], dp[N][1], dp[N][2] chính là đáp án.

4. Biểu diễn bằng Pseudo-code (Mã giả)

Nhập N
Khai báo mảng a[N+1], b[N+1], c[N+1]
Khai báo mảng dp[N+1][3]

Nhập dữ liệu cho các mảng a, b, c

// Ngày 1
dp[1][0] = a[1]
dp[1][1] = b[1]
dp[1][2] = c[1]

// Từ ngày 2 đến N
Cho i chạy từ 2 đến N:
    dp[i][0] = a[i] + lớn_nhất(dp[i-1][1], dp[i-1][2])
    dp[i][1] = b[i] + lớn_nhất(dp[i-1][0], dp[i-1][2])
    dp[i][2] = c[i] + lớn_nhất(dp[i-1][0], dp[i-1][1])

Kết quả = lớn_nhất(dp[N][0], dp[N][1], dp[N][2])
In ra Kết quả

5. Ví dụ minh họa (N=3)

Ngày 1: 10 40 70 → dp[1] = {10, 40, 70} Ngày 2: 20 50 80

• dp[2][0] = 20 + max(40, 70) = 90
• dp[2][1] = 50 + max(10, 70) = 120
• dp[2][2] = 80 + max(10, 40) = 120 Ngày 3: 30 60 90
• dp[3][0] = 30 + max(120, 120) = 150
• dp[3][1] = 60 + max(90, 120) = 180
• dp[3][2] = 90 + max(90, 120) = 210

Kết quả cuối cùng: 210.

6. Đánh giá độ phức tạp

• Thời gian: vì chúng ta chỉ duyệt qua ngày, mỗi ngày thực hiện vài phép tính so sánh đơn giản.
• Không gian: để lưu bảng dp. (Có thể tối ưu xuống nếu chỉ lưu kết quả của ngày hôm trước, nhưng với người mới bắt đầu, dùng mảng cho dễ hiểu).