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.

Author: bedao

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

Please read the guidelines before commenting.


  • -1
    orzzz  commented on Sept. 14, 2023, 2:41 a.m.

    g


  • -1
    khangnguyen1108  commented on Aug. 24, 2022, 3:53 a.m.

    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 @@


  • 5
    nguyene2p  commented on Aug. 15, 2022, 4:41 a.m.

    e đọc vẫn ko hiểu ý tưởng lắm @@. ai giải thích lại giúp e được ko ạ


    • 58
      marvinthang  commented on Aug. 15, 2022, 3:27 p.m. ← edited

      Ý 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~.

      • Trường hợp không chọn ~i~: ~dp_{i, j, k} += dp_{i - 1, j, k}~.
      • Trường hợp không chọn ~j~: ~dp_{i, j, k} += dp_{i, j - 1, k}~.
      • Trường hợp chọn ~i~ và ~j~, chỉ xảy ra khi ~a_i > b_j~: ~dp_{i, j, k} += dp_{i - 1, j - 1, k - 1}~.

      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}~.