Hướng dẫn cho Bedan Contest #01 - C - Nhảy lò cò

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Nhân xét chung

Số nguyên dương $m$ lớn nhất thỏa mãn $P$ chia hết cho $10^m$ thực chất là $min(cnt_2, cnt_5)$ với $cnt_2, cnt_5$ lần lượt là số lần xuất hiện của $2, 5$ trong $P$ khi phân tích thừa số nguyên tố.
Từ nhận xét trên, ta có thể phân tích từng phần tử của dãy $a$ dưới dạng thừa số nguyên tố thay vì nhân lại với nhau để tránh tràn số.

Subtask $1$ : $1 \le n \le 20$ .

Hint

Quay lui.

Solution

Với mỗi số nguyên dương $i$ từ $1$ đến $n$ , ta sẽ quay lui tìm cách nhảy có độ dài $i$ sao cho số điểm là lớn nhất.
Độ phức tạp của ý tưởng trên là $O(C^n_{1}+C^n_{2}+...+C^n_{n})$ hay là $O(2^n)$ .

Subtask $2$ : Không giới hạn gì thêm.

Hint

Đây thực chất là $1$ dạng của bài toán cái túi.

Solution

Gọi $dp[i][j]$ là cách nhảy ở lượt thứ $i$ để $P$ có số lượng thừa số $5$ là $j$ khi phân tích thừa số nguyên tố. Lý do tại sao lại là thừa số $5$ chứ không phải $2$ thì bạn tự hiểu bởi nó đơn giản cực :D
Bn đầau, $dp[0][0] = 0$ là tất nhiên. Nếu ta nhảy vào ô ở vị trí $pos$ thì $dp[i+1][j+pos_{cnt_5}] = max(dp[i+1][j+pos_{cnt_5}], dp[i][j]+pos_{cnt_2})$ . Nếu không thì $dp[i+1][j+cnt_5] = dp[i][j]$ , cái này quá rõ rồi.
Sau khi tính xong tất cả, kết quả của chúng ta sẽ là tổng của $max(min(j, dp[i][j]))$ với mỗi $i$ từ $1$ đến $n$ .
Độ phức tạp của ý tưởng trên là $O(n^2 \times max(a))$ .

Bình luận

Không có bình luận nào.