Hướng dẫn giải của Bedao Regular Contest 08 - NEGIKO
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.
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ả: 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}~.
Code mẫu
#include <bits/stdc++.h> using namespace std; struct Node { int value; bool isFj; bool operator<(Node const& other) const { if (value == other.value) { return isFj && !other.isFj; } return value < other.value; } }; #define NMAX 1000 #define KMAX 10 #define MOD 1000000009 unsigned int dp[2 * NMAX + 1][KMAX + 1][KMAX + 1]; int main() { int n, m, k; cin >> n >> m >> k; vector<Node> nodes; for (int i = 0; i < n; i++) { Node n; scanf("%d", &n.value); n.isFj = true; nodes.push_back(n); } for (int i = 0; i < m; i++) { Node n; scanf("%d", &n.value); n.isFj = false; nodes.push_back(n); } sort(nodes.begin(), nodes.end()); for (int i = 0; i <= k; i++) { for (int j = 0; j <= k; j++) { dp[nodes.size()][i][j] = (i == 0 && j == 0 ? 1 : 0); } } for (int pos = nodes.size() - 1; pos >= 0; pos--) { for (int i = 0; i <= k; i++) { for (int j = 0; j <= k; j++) { if (j > i) { dp[pos][i][j] = 0; } else { if (nodes[pos].isFj) { dp[pos][i][j] = (dp[pos+1][i][j] + (i > 0 ? dp[pos+1][i-1][j] : 0)) % MOD; } else { dp[pos][i][j] = (dp[pos+1][i][j] + (j > 0 ? dp[pos+1][i][j-1] : 0)) % MOD; } } } } } printf("%d\n", dp[0][k][k]); }
Bình luận
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}~.