蓝桥杯 摆花 多重背包dp

 1 #include <bits/stdc++.h> 
 2 using namespace std;
 3 int a[110];
 4 int dp[110][110]; //设dp[i][j]的值是前i种花摆放j盆的方案数
 5 const int mod = 1000007;
 6 int main() {
 7     int n, m;
 8     cin >> n >> m;
 9     for (int i = 1; i <= n; i++) {
10         cin >> a[i];
11     }
12     //前1种花，也就是第一种花，摆放a[1]盆就一种方案
13     for (int i = 0; i <= a[1]; i++) {
14         dp[1][i] = 1;
15     }
16     //前i种花，摆放0盆就一种方案
17     for (int i = 1; i <= n; i++) {
18         dp[i][0] = 1;
19     }
20     //前i种花，摆放j盆共f[i][j]=f[i][j]+f[i-1][j-k]种
21     for (int i = 2; i <= n; i++) { //花的种类数从2~n 
22          for (int j = 1; j <= m; j++) { //可以摆的盆数，从1~m 
23             for (int k = 0; k <= a[i] && k <= j; k++) { //k是这种花选几个 
24                 dp[i][j] = (dp[i][j] % mod + dp[i - 1][j - k] % mod) % mod;
25             }
26         }
27     }
28     cout << dp[n][m] << endl;
29     return 0;
30 }