AcWing 1487. 取硬币
原题链接
简单
作者:
我要出去乱说
,
2021-02-03 16:26:51
,
所有人可见
,
阅读 445
#include <iostream>
using namespace std;
const int N = 1e5 + 10, MOD = 1e9 + 7;
int n1, n2, m;
int f[N];
int main()
{
cin >> n1 >> n2 >> m;
f[0] = 1; //状态初始化:没有硬币即什么都不选的选法
for (int i = 1; i <= n1; i ++ ) //普通硬币:完全背包
{
int p; //f[i][j]表示只取前i个硬币能组成j的组合数
cin >> p; //未优化的二维状态转移方程:f[i][j] = f[i - 1][j] + f[i][j - p]
for (int j = p; j <= m; j ++ ) f[j] = (f[j] + f[j - p]) % MOD; //可以重复:从前往后遍历
}
for (int i = 1; i <= n2; i ++ ) //纪念硬币:0-1背包
{
int p;
cin >> p; //未优化的二维状态转移方程:f[i][j] = f[i - 1][j] + f[i - 1][j - p]
for (int j = m; j >= p; j -- ) f[j] = (f[j] + f[j - p]) % MOD; //不能重复:从后往前遍历
}
cout << f[m] << endl;
return 0;
}