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

· · 题解

题目传送门

题意

给定 n 个数，每个数可以用无限次。求无法组成的数有多少个，如果有无限个就输出 -1。

思路

做题先看标签：动态规划+数论。在脑子里面规划一下，输出 -1 用数论，输出正常答案用动规。
至于 -1 怎么判，相信大家都有思路了。如果这 n 个数不互质（最小公因数不等于 1），那么就输出 -1。为什么呢？假设这 n 个数的最小公因数为 g，那么必须是 g 的倍数才能被这 n 个数组合出来。举个栗子，4 和 6 这两个数的最小公因数是 2，必须是 2 的倍数的数才有可能被组合出来。
接下来是输出正常答案了。我们先设定状态，f_i 表示能否组合出 i。状态转移方程很好推，我们设输入的长度为 n 的序列叫 a，枚举一个 j ，如果 f_{i-a_j}=1 的话那么 f_i=1，反之则为 0。但是我们要到什么时候结束呢？设序列 a 中的最小值为 minn，则在出现连续 minn 次为 f_i 为 1 的时候退出。由于不确定长度，我们可以用 vector 存下 f 数组。这里注意肯定可以凑出 0 个汤圆，所以 f_0=1，可以在最开头这样写 f.push_back(1)。更具体的实现方法见代码。

代码

#include <bits/stdc++.h>
using namespace std;
int n, g, cnt, ans, a[30];
vector<bool> f;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), g = __gcd(g, a[i]);
    if (g != 1)
    {
        printf("-1");
        return 0;
    }
    sort(a + 1, a + n + 1), f.push_back(1);
    for (int i = 1; cnt < a[1]; i++)
    {
        bool flag = 0;
        for (int j = 1; j <= n && a[j] <= i; j++)
            if (f[i - a[j]])
            {
                flag = 1;
                break;
            }
        f.push_back(flag);
        if (flag)
            cnt++;
        else
            cnt = 0, ans++;
    }
    printf("%d", ans);
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。
题目传送门