codeforce543A_完全背包+滚动数组

题目链接：http://codeforces.com/contest/543/problem/A

题意：有n个程序员，m行代码，最多bug数为b

让这n个程序员完成这项任务，问有多少种分配方法，得到的答案取模mod

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #define LL long long
 6 using namespace std;
 7 
 8 const int N = 502;
 9 int bug[N], dp[2][N][N];
10 int main()
11 {
12     int n, m, b;
13     LL mod;
14     while(~scanf("%d%d%d%I64d", &n, &m, &b, &mod))
15     {
16         LL res = 0;
17         memset(dp, 0, sizeof(dp));
18         for(int i = 0; i <= n; i++)
19             dp[i % 2][0][0] = 1;
20         for(int i = 1; i <= n; i++)
21             scanf("%d", bug + i);
22         for(int i = 1; i <= n; i++)//前i个人
23         {
24             for(int j = 1; j <= m; j++)//前i个人写j行代码
25             {
26                 for(int k = 0; k <= b; k++)//前i个人写j行代码出k个bug时的分配方法个数
27                 {
28                     if(k < bug[i]) 
29                         dp[i % 2][j][k] = dp[(i - 1) % 2][j][k] % mod;
30                     else
31                         dp[i % 2][j][k] = (dp[(i - 1) % 2][j][k] + dp[i % 2][j - 1][k - bug[i]]) % mod;
32                 }
33             }
34         }
35         for(int i = 0; i <= b; i++)
36             res = (res + dp[n % 2][m][i]) % mod;
37         printf("%I64d
", res);
38     }
39     return 0;
40 }