货币系统类的题（计数型DP）

---

前言

关于货币系统原版的相关介绍在这：货币系统（求方案数的背包）。

---

1. 整数划分

一个正整数 $n$ 可以表示成若干个正整数之和，形如：$n=n_1+n_2+\dots +n_k$，其中 $n_1\ge n_2\ge \dots \ge n_k,k\ge 1$。

我们将这样的一种表示称为正整数 $n$ 的一种划分。

现在给定一个正整数 n，请你求出 $n$ 共有多少种不同的划分方法。

输入格式
共一行，包含一个整数 $n$。

输出格式
共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 $10^9+7$ 取模。

数据范围
$1\le n\le 1000$

输入样例:

5
1

输出样例：

7
1

---

C++代码

#include 
#include 
using namespace std;
typedef long long ll;

const int N = 1010;
const ll mod = 1e9 + 7;

int m;
ll f[N];

int main(){
    cin >> m;
    f[0] = 1;        //初始化，啥都没凑出来是一种方案
    for(int i = 1;i <= m;i ++){     //面值从1 ~ m
        int v;
        v = i;

        for(int j = v;j <= m;j ++){
            f[j] = (f[j] + f[j - v]) % mod;
        }
    }

    cout << f[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

---

2. 买书

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

输入格式
一个整数 n，代表总共钱数。

输出格式
一个整数，代表选择方案种数。

数据范围
$0\le n\le 1000$

输入样例1：
20
输出样例1：
2
输入样例2：
15
输出样例2：
0
输入样例3：
0
输出样例3：
1
1
2
3
4
5
6
7
8
9
10
11
12

---

C++代码

#include 
using namespace std;

const int N = 1010;

int n;
int mon[] = {10, 20, 50, 100};
int f[N];

int main(){
    cin >> n;
    f[0] = 1;
    for(auto v : mon){
        for(int i = v;i <= n;i ++){
            f[i] += f[i - v];
        }
    }
    
    cout << f[n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

3. 货币系统Ⅱ（求最大无关向量组）

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。

为了方便，我们把货币种数为 $n$、面额数组为 $a[\mathrm{1..}n]$ 的货币系统记作 $(n,a)$。

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i]\times t[i]$ 的和为 $x$。

然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。

例如在货币系统 $n=3,a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。

他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。

他们希望你来协助完成这个艰巨的任务：找到最小的 $m$。

输入格式
输入文件的第一行包含一个整数 T，表示数据的组数。

接下来按照如下格式分别给出 T 组数据。

每组数据的第一行包含一个正整数 n。

接下来一行包含 n 个由空格隔开的正整数 a[i]。

输出格式
输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与 (n,a) 等价的货币系统 (m,b) 中，最小的 m。

数据范围
1≤$n$≤100,
1≤$a[i]$≤25000,
1≤$T$≤20

输入样例：

2 
4 
3 19 10 6 
5 
11 29 13 19 17 
1
2
3
4
5

输出样例：

2
5
1
2

---

根据题意理解，其实就是把$(n,a)$这个货币系统简化，简化成在系统里任意面值的a[i]均不能被其它货币线性地表示出。
例如对于样例1：
19可以由10 + 3 + 6线性组合出来，因此19在这个系统里就是冗余的，可以剔除，同理6也可已被3 + 3线性地表示出来，因此剔除掉，最后就只剩下3、10这两个数了，因为它们不能被互相线性表示出来，所以3、10就是样例1的最简化货币系统。

那么这样一描述，其实也很容易联想到这就像是线性代数里求最大无关向量组的个数。

以下引自一位佬的博客：货币系统【完全背包求解最大无关向量组个数】。

那么对于货币a[i]，要看它是否是冗余的，其实就是看它能被其它货币值凑出来的方案个数

• 若为0，说明这个货币系统没它不行，所以a[i]要作为这个系统的一个基，同时统计$b$的货币种数+1。
• 若不为0，说明它可以被凑出来，则a[i]为冗余的，可以剔除掉。

其实发现这个统计方案的做法，又回归到了上面讲的完全背包的DP模型，那么这里的f[j]：凑出非负整数j的方案数。

不过相对于前面有点变化的是，这里还引入了一点筛法的思想，即每次判断一下f[a[i]]的值，不为0则直接continue就可以了。

注*：我们知道对于货币a[i]，它若能凑则只可能被那些都比它小的货币值线性相加起来，所以为了能正确引入DP模型，将a[]进行sort一遍，这样就能确保f[j] += f[j - a[i]];这个转移方程是正确地统计到了凑a[i]的方案数。

更多具体的解释还可以再看上面放的佬の链接。

C++代码

#include 
#include 
#include 
using namespace std;

const int N = 25010;        //这个根据a[]决定的

int f[N], a[110];       //f[j]：凑出非负整数j的方案数
int n, T, res;

int main(){
    cin >> T;
    while(T --){
        res = 0;
        cin >> n;
        for(int i = 0;i < n;i ++)       cin >> a[i];
        sort(a, a + n);
        int m = a[n - 1];           //a[n]是最大的数
        memset(f, 0, sizeof f);
        f[0] = 1;       //初始划定方案数为1
        
        for(int i = 0;i < n;i ++){
            if(f[a[i]])     continue;       //被筛掉了
            
            //f[a[i]] = 0 ————> false，说明它不存在被线性组合的方案，即它是一个基，进行下面的操作
            res ++;
            
            for(int j = a[i];j <= m;j ++){      //完全背包的计数DP模型
                f[j] += f[j - a[i]];
            }
        }
        
        cout << res << 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
27
28
29
30
31
32
33
34
35
36
37