Editorial for Bedao Regular Contest 08 - NEGIKO
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Vì ~N~, ~M~ và ~K~ khá nhỏ nên ta có thể quy hoạch động với ~O(N \times M \times K)~.
Với ~dp_{i,j,k}~ là số lượng ~k~ thẻ bải được chọn sau khi ta xét ~i~ thẻ bài đầu tiên của ~Neko~ và ~j~ thẻ bài đầu tiên của đối thủ. Ta có công thức chuyển trạng thái:
~dp_{i,j,k}~ = ~dp_{i-1,j,k} + dp_{i,j-1,k} - dp_{i-1,j-1,k}~
Nếu thẻ bài thứ ~i~ của ~Neko~ lớn hơn thẻ bài thứ ~j~ của đối thủ. Ta sẽ cộng ~dp_{i-1,j-1,k-1}~ vào ~dp_{i,j,k}~.
Comments
g
Em vẫn chưa hiểu ban đầu mình phải xử lý làm sao @@ Mình có cần phải duyệt hết khi i = 1 , j = 1 , k = 1 để lấy giá trị ban đầu không z mng @@
e đọc vẫn ko hiểu ý tưởng lắm @@. ai giải thích lại giúp e được ko ạ
Ý tưởng là sort 2 dãy ~a, b~ tăng dần xong chọn lần lượt các thẻ bài ~(i, j)~ để ~a_i > b_j~. Khi mà xét đến ~dp_{i, j, k}~, ta có 3 lựa chọn ở trạng thái trước là không chọn ~i~, không chọn ~j~ và chọn ~i~, ~j~.
Nhưng ta nhận thấy là trường hợp không chọn ~i~ và trường hợp không chọn ~j~ nó có phần trùng nhau, đó là các cách chọn mà không chọn cả ~i~ và ~j~, khi đó các cách chọn này bị tính 2 lần, số cách chọn không chọn cả ~i~ và ~j~ là ~dp_{i - 1, j - 1, k}~ nên ta cần: ~dp_{i, j, k} -= dp_{i - 1, j - 1, k}~.