Hướng dẫn giải của Giống bò cân bằng (Dễ)

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Giống bò cân bằng (Dễ)

Hướng tiếp cận

Quy hoạch động 2D: $d p [i] [a]$ = số cách gán $i$ ký tự đầu với giống A có $a$ dấu ( chưa khớp.

Nhận xét quan trọng

Số dấu ( chưa khớp của giống B = tổng dấu ( chưa khớp tính đến vị trí $i$ trừ $a$ . Vậy B được xác định bởi $(i, a)$ → giảm từ $O (N^{3})$ xuống $O (N^{2})$ .
Gán ký tự thứ $i$ cho giống A hay B đều hợp lệ nếu số ( chưa khớp tương ứng không âm.
Modulo $2012$ .

Thuật toán

DP tiến từ đầu đến cuối chuỗi, cập nhật $d p [a]$ tại mỗi bước. Kết quả là $d p [0]$ sau khi xử lý toàn bộ chuỗi (khi tổng dấu ( chưa khớp = 0).

Độ phức tạp

Thời gian: $O (N^{2})$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.