宁德蕉城住房和城乡建设部网站成都seo整站
题意
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入与数据范围
第一行包含一个整数NNN。(1<=N<=100)(1 <= N <= 100)(1<=N<=100)
以下NNN行每行包含一个整数AiAiAi。(1<=Ai<=100)(1 <= Ai <= 100)(1<=Ai<=100)
算法(裴蜀定理,背包问题)
先给出两个数xxx,yyy是否能凑出最大数的问题。
- 如果xxx和yyy的最大公约数是1,那么它们存在不能够凑出的最大数,并且它们不能凑出的最大数是:(x−1)×(y−1)−1(x - 1) \times (y - 1) - 1(x−1)×(y−1)−1
- 在本题中,不能够凑出最大数意味着:他们不能凑出的数是有限的,因为不能够凑出的最大数为upupup,等价着大于upupup的所有数都能够被凑出,那么不能够凑出的数只可能在区间[1,up][1, up][1,up]中,显然,这个区间中的数是有限的。
所以我们先把所有蒸笼所装的包子数的最大公约数ddd给算出来。
// 最大公约数代码
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
如果ddd不等于1,那么他们不存在不能够凑出的最大数,等价于不能够凑出的包子数量为无限个INF(infinity)。
否则我们就用动态规划来解决ddd等于1的情况,其实这种情况很简单。我们大致估计一下最大的不能够被凑出的包子数量的量级为:(100−1)×(100−1)−1(100 - 1) \times (100 - 1) - 1(100−1)×(100−1)−1,即为100001000010000量级。
我们定义状态数组:boolf[110][10010]bool \enspace f[110][10010]boolf[110][10010]
其中f[i][j]f[i][j]f[i][j]表示这A1∼AiA1 \sim AiA1∼Ai这些iii个蒸笼是否能够凑出数量为jjj的包子。
起初f[0][0]=truef[0][0] = truef[0][0]=true表示着000个包子可以被凑出,因为我们不需要选择任何蒸笼就已经凑出000个包子。
状态计算:f[i][j]=f[i−1][j]f[i][j] = f[i - 1][j]f[i][j]=f[i−1][j] 和 f[i][j]=f[i][j−a[i]](j>=a[i])f[i][j] = f[i][j - a[i]] \enspace (j >= a[i])f[i][j]=f[i][j−a[i]](j>=a[i])
AC代码(C++)
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, M = N * N;int n;
int a[N];
bool f[N][M];int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}int main() {cin >> n;for (int i = 1; i <= n; i ++) cin >> a[i];int d = 0;for (int i = 1; i <= n; i ++) d = gcd(d, a[i]);if(d != 1) cout << "INF" << "\n";else {f[0][0] = true;for (int i = 1; i <= n; i ++ ) {for (int j = 0; j < M; j ++) {f[i][j] = f[i - 1][j];if(j >= a[i]) {f[i][j] |= f[i][j - a[i]];}}}int res = 0;for (int i = 0; i < M; i ++)if(!f[n][i]) res ++ ;cout << res << "\n";}return 0;
}