包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入描述
第一行包含一个整数
N
(
1
≤
N
≤
100
)
N(1 \leq N \leq100)
N(1≤N≤100)。
以下
N
N
N 行每行包含一个整数
A
i
(
1
≤
A
i
≤
100
)
A_i(1 \leq A_i \leq 100)
Ai?(1≤Ai?≤100)。
输出描述
一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。
输入输出样例
示例 1
输入
2
4
5
输出
6
样例说明
凑不出的数目包括：1, 2, 3, 6, 7, 11。
示例 2
输入
2
4
6
输出
INF
样例说明
所有奇数都凑不出来，所以有无限多个
思路
- 看起来似曾相识，隐隐约约有一点感觉，之后想起了线性代数中的线性方程组通解的组成，极大线性无关组，向量的基底，矩阵的秩等内容，但还是没有头绪
- 不过有一点启发：在一组向量中找极大线性无关组，每个向量都可以由这个极大线性无关组表示出来。
- 如果我能在给出的那些包子数里面找到几个数(作为“极大无关组”)，使得对于任何包子数，都可以用这些数表示出来，那么就有有限个包子数不能被表示出来。
- 那么对于这道题而言，能找到“极大无关组”就可以输出有多少个包子数不能被凑出，否则就输出INF
- 怎么才算“能找到极大无关组呢”？
- 原问题可以转化为一个解方程的问题，即：给出的每个包子数作为系数，每笼包子的笼数是未知数(自然数)，顾客要求的数目为常数，即
a
1
?
x
1
+
a
2
?
x
2
+
?
+
a
n
?
x
n
=
b
a_1*x_1+a_2*x_2+\dots+a_n*x_n=b
a1??x1?+a2??x2?+?+an??xn?=b其中
(
a
1
,
a
2
,
…
,
a
n
)
(a_1,a_2,\dots,a_n)
(a1?,a2?,…,an?)是所给出的每笼的包子个数，
b
b
b是顾客要求的包子数目，我们要求的是
(
x
1
,
x
2
,
…
,
x
n
)
(x_1,x_2,\dots,x_n)
(x1?,x2?,…,xn?)，即包子的笼数
- 然后参考别人的题解，发现了一个我不知道的定理，那么就不必再纠结于“极大无关组”了，用以下定理解题更清晰
- 裴蜀定理：任意两个数的组合必定是它们最大公约数的倍数。
- 推广：如果
n
n
n个数的最大公约数是
k
k
k，那么它们的组合是
k
k
k的倍数，如果
k
=?
1
k\not =1
k?=1，则必然有无限个数无法被组合出来
- 如果每笼包子数目的最大公约数不是1，应该输出INF
- 如果给出的这些包子数互质，即最大公约数为1，那么由定理可知，是有有限个数不能被凑出来的，应该输出个数
- 但是题目并没有说顾客要求的包子数的上限是多少，这里只能确定个大概：
- 因为如果只有两个互质的数
a
,
b
a,b
a,b的话，那么这个"表示不出来的数"的上限为
u
=
(
a
?
1
)
?
(
b
?
1
)
?
1
u=(a-1)*(b-1)-1
u=(a?1)?(b?1)?1
- 我觉得用这种思路确定上界很不错：当数字更多的时候，这个上界会变小，而题目数据限定
A
i
A_i
Ai?在100之内，那么用10000作为上限比较好(实际上10000已经比原有的上界更大了)
- 到此正式理清思路，开始解题
- 完全背包(动态规划)
-
d
p
dp
dp数组设为布尔数组即可，为真表示能凑出，为假表示不能凑出，最终统计为假的个数，即为答案
- 初始化
d
p
[
0
]
[
0
]
=
1
dp[0][0]=1
dp[0][0]=1，因为0个包子能凑出来
- 状态转移方程
i
f
(
j
≥
a
[
i
]
)
:
d
p
[
i
]
[
j
]
=
d
p
[
i
?
1
]
[
j
]
∣
∣
d
p
[
i
]
[
j
?
a
[
i
]
]
;
if (j\geq a[i]):dp[i][j]=dp[i-1][j]||dp[i][j-a[i]];
if(j≥a[i]):dp[i][j]=dp[i?1][j]∣∣dp[i][j?a[i]];
e
l
s
e
:
d
p
[
i
]
[
j
]
=
d
p
[
i
?
1
]
[
j
]
;
else :dp[i][j]=dp[i-1][j];
else:dp[i][j]=dp[i?1][j];
代码如下
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VAL = 10000;
vector<int> a;
vector<vector<bool>> dp;
int n;
int gcd(int m, int n) {
if (n == 0) return m;
return gcd(n, m % n);
}
int main() {
scanf("%d", &n);
int cd = 0;
int i = 0, j = 0;
a.resize(n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
cd = gcd(cd, a[i]);
}
if (cd == 1) {
dp.resize(n + 1);
for (i = 0; i <= n; i++) {
dp[i].resize(MAX_VAL, false);
}
dp[0][0] = true;
for (i = 1; i <= n; i++) {
for (j = 0; j < MAX_VAL; j++) {
dp[i][j] = dp[i - 1][j] ||
((j >= a[i - 1]) ? dp[i][j - a[i - 1]] : false);
}
}
int ans = 0;
for (i = 0; i < MAX_VAL; i++) {
if (!dp[n][i]) ans++;
}
printf("%d\n", ans);
} else {
printf("INF\n");
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VAL = 10000;
vector<int> a;
vector<bool> dp;
int n;
int gcd(int m, int n) {
if (n == 0) return m;
return gcd(n, m % n);
}
int main() {
scanf("%d", &n);
int cd = 0;
int i = 0, j = 0;
a.resize(n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
cd = gcd(cd, a[i]);
}
if (cd == 1) {
dp.resize(MAX_VAL, false);
dp[0] = true;
for (i = 1; i <= n; i++) {
for (j = 0; j < MAX_VAL; j++) {
if (j >= a[i - 1]) dp[j] = dp[j] || dp[j - a[i - 1]];
}
}
int ans = 0;
for (i = 0; i < MAX_VAL; i++) {
if (!dp[i]) ans++;
}
printf("%d\n", ans);
} else {
printf("INF\n");
}
return 0;
}
|