【每日一题15】AcWing 1371. 货币系统

发表于 更新于 分类于 Valine：
本文字数： 34 阅读时长 ≈ 1 分钟

Day15 AcWing 1371. 货币系统

思路

  1. 背包问题

代码

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 30, M = 10010;

int n, m;
LL f[N][M];

int main()
{
    cin >> n >> m;
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (j >= v) f[i][j] += f[i][j - v];
        }
    }
    cout << f[n][m] << endl;
    return 0;
}
一维空间写法
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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 30, M = 10010;

int n, m;
LL f[M];

int main()
{
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = v; j <= m; j ++ )
            f[j] = f[j] + f[j - v];
    }
    cout << f[m] << endl;
    return 0;
}