AcWing 451. 摆花
原题链接
简单
作者:
我是java同学
,
2023-02-06 16:13:18
,
所有人可见
,
阅读 127
dp 多重背包
- 多重背包的简化版
- 将状态数代入方程看如何初始化
- 数据范围提示花盆的数量可以从
0
开始枚举,j
从0
开始循环
#include <iostream>
using namespace std;
const int N = 110, mod = 1e6 + 7;
int n, m;
int a[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
f[0][0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; k <= a[i]; k ++ )
if (j >= k)
f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
cout << f[n][m] << endl;
}