cf#302 C. Writing Code dp

点击打开链接

题意：有n个程序员，第i个程序员每行会有ai个bug，然后让你按着顺序安排程序员，问你有多少种安排方法，可以使得写m行的bug最多b个

思路：

dp[i][j]表示写i行bug数有j个的方法数

转移方程和背包问题类似 

最后扫一遍统计一下就好

代码：

#include <bits/stdc++.h>using namespace std;const int maxn = 500+10;int a[maxn],dp[maxn][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 k=1; k<=n; k++)        for(int i=1; i<=m; i++)            for(int j=a[k]; j<=b; j++)                dp[i][j] = (dp[i][j] + dp[i-1][j-a[k]]) % mod;    long long ans = 0;    for(int i=0; i<=b; i++)        ans = (ans+dp[m][i])%mod;    cout << ans << endl;}