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

· · 题解

思路

本题可以使用动态规划。设 dp_i 为个数为 i 的汤圆是否可以买到，等于 1 表示可以买到，等于 0 表示不能买到，然后统计有多少个 dp_i=0 这个就是答案。当 dp_{i-a_j}=1 时，dp_i=1。

难点

1.如何判断有无限种数量的汤圆不能买到？

设所有数的最大公约数为 x，如果 x \ne 1，那么输出 -1。

证明：

当 x \ne 1 时，只能凑出 x 的倍数个汤圆，而非 x 的倍数的数有无数个，所以要输出 -1。

2.dp 上限是多少？

对于 n=2 时动规上限的证明，可以参考这道题目的题解。那么当 n 增大时，不能买到的汤圆个数上限的值不可能变高，只有可能变低，所以我们动规上限为 \max(a_ia_j-a_i-a_j)(1 \le i,j \le n,\gcd(a_i,a_j)=1)，这个式子的最大值不会超过 100*99-100-99=9701，所以我们可以只枚举到 9701，但保险起见，我们就枚举到 10^6。

CODE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef const ll cll;
typedef vector<ll>vll;
typedef string str;
typedef pair<ll, ll>pll;
#define pb push_back
#define st first
#define nd second
cll llmi = -9187201950435737472;
cll llma = 9187201950435737471;
cll N=1e6;
ll n,a[1000005],m,x,ans;
bool dp[1005005];
int main() {
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        x=__gcd(a[i],x),m+=a[i];
        dp[a[i]]=1;
    }
    if(x!=1){printf("-1");return 0;}
    for(int i=1;i<=N;i++){
        for(int j=1;j<=n;j++){
            if(i-a[j]>0)dp[i]|=dp[i-a[j]];
        }
        if(!dp[i])ans++;
    }
    printf("%lld",ans);
    return 0;
}