Hướng dẫn giải của Atcoder Educational DP Contest M - Candies
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.
Gọi ~dp[i][j]~ là số cách chia ~j~ viên kẹo cho ~i~ đứa trẻ đầu tiên.
Ta có:
Độ phức tạp tính toán: ~O(N\cdot K^2)~.
Nếu áp dụng công thức trên thì ta phải sử dụng mảng hai chiều để lưu trữ tuy nhiên để tính dòng ~i~ ta chỉ cần dòng ~i-1~.
Như vậy, gọi ~dp[j]~ là số cách chia ~j~ viên kẹo cho ~i~ đứa trẻ đầu tiên và ~dq[j]~ là số cách chia ~j~ viên kẹo cho ~i-1~ đứa trẻ đầu tiên. Sau khi tính toán xong ta chỉ cần lưu mảng ~dp~ vào mảng ~dq~.
Nhận thấy ~dp[j]~ nhận giá trị là tổng từ ~dq[j-a_i]~ tới ~dq[j]~. Chính vì thế mà với mỗi ~dp[j]~ chúng ta phải duyệt lại từ ~j-a_i~ tới ~j~ khiến cho chi phí tính toán cao.
Ta có thể giải quyết vấn đề trên bằng cách tạo thêm mảng ~S~, với ~S_j = dq[0] + dq[1] + dq[2] + ... + dq[j]~. Mảng ~S~ gọi là mảng cộng dồn.
Khi đó, ta có thể tính ~dp[j] = S[j] - S[j-a_i-1]~.Chínhh vì không cần phải duyệt lại nữa mà độ phức tập tính toán giảm còn ~O(N\cdot K)~.
#include <bits/stdc++.h> using namespace std; const int MAXK = 100000; const int MOD = 1000000007; int add(int i, int j) { if ((i += j) >= MOD) i -= MOD; return i; } int sub(int i, int j) { if ((i -= j) < 0) i += MOD; return i; } int main() { cin.tie(0)->sync_with_stdio(0); int n, k, a; cin >> n >> k; static int dp[MAXK + 1], dq[MAXK + 1]; dp[0] = 1; for (int i = 1; i <= n; ++i) { cin >> a; for (int j = 1; j <= k; ++j) dp[j] = add(dp[j - 1], dp[j]); for (int j = 0; j <= k; ++j) dq[j] = sub(dp[j], (j > a ? dp[j - a - 1] : 0)); swap(dp, dq); } cout << dp[k] << '\n'; }
Bình luận
Bài này không dùng mảng dq vẫn đúng mà
Xin phép sửa cmt vì mình cmt nhầm ạ :((
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
dp ở đây là mảng cộng dồn cho phần tính dq ở i - 1 trước đó. Còn dq được tính bằng công thức QHĐ dq[j] = dp[j] - dp[j - a - 1]. Khi tính xong dq ở i thì ta update lại dp = dq.