自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:18:23，当前版本为作者最后更新于2025-07-20 17:40:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意

给定 $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;
}

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