AcWing 1487. 取硬币
宋标 Lv5
  2022-08-18 02:31:44 2022-08-18 02:31    

题目

现在有 种面值的硬币，其中前 种为普通币，可以取任意枚，后 种为纪念币，每种最多只能取 枚，每种硬币有一个面值，问能用多少种方法拼出 的面值？

输入格式

第一行包含三个整数 ，分别表示普通币种类数，纪念币种类数和目标面值；

第二行 个整数，第 种普通币的面值 。保证 为严格升序；

第三行 个整数，第 种纪念币的面试 。保证 为严格升序。

输出格式

共一行，包含一个整数 ，表示方法总数对 取模后的结果。

注意，不要忘记取模。

数据范围

对于 的数据，保证 。
对于 的数据，保证 。

输入样例：

3 1 5
1 2 3
1

输出样例：

9

样例解释

(x) 代表面值为x的普通币，[x]代表面值为x的纪念币，样例所有方法数如下：

(1)(1)(1)(1)(1)
(1)(1)(1)(2)
(1)(1)(3)
(1)(2)(2)
(2)(3)
(1)(1)(1)(1)[1]
(1)(1)[1](2)
(1)[1](3)
[1](2)(2)

题解

2维dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>

using namespace std;

const int N = 100010, MOD = 1e9 + 7;

/*
    f[i, j]前i个硬币，面值是j的所有集合，属性：数量
*/
int f[110][N];

int main()
{
    int n1, n2, m;
    cin >> n1 >> n2 >> m;

    for (int i = 1; i <= n1 + n2; ++ i) f[i][0] = 1;

    // 完全背包(不限制数量)
    for (int i = 1; i <= n1; ++ i)
    {
        int p;
        cin >> p;
        for (int j = 1; j <= m; ++ j)
        {
            f[i][j] = f[i - 1][j];
            if (j >= p)
                // f[i][j] = f[i - 1][j] + f[i - 1][j - p1] + f[i - 1][j - p2] + ... + f[i - 1][j - pk]
                // f[i][j - p] = f[i - 1][j - p1] + f[i - 1][j - p2] + ... + f[i - 1][j - pk]
                f[i][j] = (f[i][j] + f[i][j - p]) % MOD;
        }

    }

    // 01背包(选与不选)
    for (int i = n1 + 1; i <= n1 + n2; ++ i)
    {
        int p;
        cin >> p;
        for (int j = 1; j <= m; ++ j)
        {
            f[i][j] = f[i - 1][j];
            if (j >= p)
                // 总数量 = 没选i枚硬币 + 选i枚硬币(减去这枚硬币面值就等于选了这枚硬币)
                f[i][j] = (f[i][j] + f[i - 1][j - p]) % MOD;
        }
    }

    cout << f[n1 + n2][m] << endl;

    return 0;

}

1维优化dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>

using namespace std;

const int N = 100010, MOD = 1e9 + 7;

/*
    f[i, j]前i个硬币，面值是j的所有集合，属性：数量
*/
int f[N];

int main()
{
    int n1, n2, m;
    cin >> n1 >> n2 >> m;

    f[0] = 1;

    // 完全背包(不限制数量)
    for (int i = 1; i <= n1; ++ i)
    {
        int p;
        cin >> p;
        for (int j = p; j <= m; ++ j)
        {
            // f[i][j] = f[i - 1][j] + f[i - 1][j - p1] + f[i - 1][j - p2] + ... + f[i - 1][j - pk]
            // f[i][j - p] = f[i - 1][j - p1] + f[i - 1][j - p2] + ... + f[i - 1][j - pk]
            f[j] = (f[j] + f[j - p]) % MOD;
        }

    }

    // 01背包(选与不选)
    for (int i = 1; i <= n2; ++ i)
    {
        int p;
        cin >> p;
        for (int j = m; j >= p; -- j)
        {
            // 总数量 = 没选i枚硬币 + 选i枚硬币(减去这枚硬币面值就等于选了这枚硬币)
            f[j] = (f[j] + f[j - p]) % MOD;
        }
    }

    cout << f[m] << endl;

    return 0;

}
 评论