codeforces 543A 完全背包

codeforces 543A 完全背包

安排n個人寫m行代碼，每個人每行會出a[i]個bug，求最多出現b個bug的方案數。

一個二維的完全背包，每個人有兩個狀態：寫j行代碼出k個bug

dp[i][j][k] 前i個程序員寫錢j行出現k個bug的方案數。

dp[i][j][k] = dp[i][j-1][k-a[i]] + dp[i-1][j][k];

注意這裡數組會超內存，需要用滾動數組。

#include 
using namespace std;

int n, m, b;
long long mod;

long long a[505];

long long dp[2][505][505];

int main () {

    cin >> n >> m >> b >> mod;

    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }

    for (int i=1; i<=n; i++) dp[i % 2][0][0] = 1L;

    for (int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            for (int k=0; k<=b; k++) {
                if (k < a[i]) dp[i % 2][j][k] = dp[(i-1) % 2][j][k] % mod;
                else dp[i % 2][j][k] = (dp[i % 2][j-1][k - a[i]] + dp[(i-1) % 2][j][k]) % mod;
            }
        }
    }

    long long ans = 0;

    for (int i=0; i<=b; i++) {
        ans = (ans + dp[n % 2][m][i]) % mod;
    }

    cout << ans % mod << endl;

    return 0;
}