Editorial for Atcoder Educational DP Contest M - Candies


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.

Gọi ~dp[i][j]~ là số cách chia ~j~ viên kẹo cho ~i~ đứa trẻ đầu tiên.

Ta có:

~dp[i][j] = \sum dp[i-1][j']~ ~(0 \leq j - j' \leq a_i)~.

Độ 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';
}

Comments

Please read the guidelines before commenting.



  • 2
    tronghuy  commented on April 15, 2023, 2:52 p.m.

    Xin phép sửa cmt vì mình cmt nhầm ạ :((


  • 0
    thaihoang78  commented on Oct. 2, 2022, 2:03 a.m.

    Cho mình hỏi là vì sao lại tính dp[j] như mảng cộng dồn và tính dq[j] như công thức quy hoạch động dp[j] ở phần lời giải và sau đó là swap chúng với nhau vậy ạ?


    • 0
      QioCass  commented on Nov. 5, 2022, 7:47 a.m.

      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.