Luogu-题解：B4290 [蓝桥杯青少年组省赛 2022] 组合

传送门

关于无解的情况

我们先计算一下这些数的最大公约数，如果他们的最大公约数不等于 $1$，因为这组数据下我们只能买到 $sum$ 及其倍数个的汤圆。所以遇到这种情况直接输出 $-1$。

DP

与其说是动态规划，不如说是递推，我们设置 $f_{a_i}$ 为 $1$，代表能够凑出（$a_i$ 为所给出的规格），然后如果 $f_{i-a_j}$ 是 $1$，那么 $f_i$ 也应该是 $1$，因为可以转化为 $f_{i-a_j}$ 再加上一个 $i$ 号规格的汤圆。对于每一个数，我们判断它是否可以凑出来，最后没有被赋值为 $1$ 的就是答案。

#include <bits/stdc++.h>
const int N = 1e6 + 10;
typedef long long ll;
using namespace std;
int num[30], n;
int counter = 0, tp = 0, maxcounter = 0;
bool check[N];

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	cin >> n;
	for(int i = 0;i <= n;i++) cin >> num[i];
	sort(num, num + n);
	int pd = num[0];
	for(int i = 0;i <= n;i++) {
		pd = gcd(pd, num[i]);
	}
	if (pd != 1) {
		cout << -1;
		return 0;
	}
	memset(check, false, sizeof check);
	check[0] = true;
	for(int i = 1;i <= N;i++) {
		for(int j = 0;j <= n;j++) {
			if (num[j] > i) break;
			if (check[i - num[j]]) {
				check[i] = true;
				break;
			}
		}
		if (check[i]) {
			tp++;
			if (tp >= num[0]) {
				maxcounter = i - num[0];
				break;
			}
		} else counter++,tp = 0;
	}
	cout << counter;
}