有n个人,要写m行代码,第i个人每写一行会出现ai个bug,每个人可以写任意行,但总bug数不能超过b个,求总方案数
dp[j][k] 表示有j行代码k个bug的方法数,
所有转移方程为:类似一维完全背包
dp[j + 1][k + a[i]] += dp[j][k]
#include <bits/stdc++.h> using namespace std; const int maxn = 1005; int dp[maxn][maxn]; int a[maxn]; int main() { int n, m, b, mod; cin >> n >> m >> b >> mod; for (int i = 1; i <= n; i++) cin >> a[i]; dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= b; k++) { dp[j + 1][k + a[i]] += dp[j][k]; dp[j + 1][k + a[i]] %= mod; } } } int ans = 0; for (int i = 0; i <= b; i++) { ans += dp[m][i]; ans %= mod; } cout << ans << endl; return 0; }