【篮球杯 DP+数论】包子凑数

小鱼儿 2024-03-25 06:16 56阅读 0赞

**hard**

[AcWing 1226. 包子凑数 - AcWing][AcWing 1226. _ - AcWing]

题意：

![0f94025a58d2221aeddac3a4139f8933.png][]

思路：

首先有个结论：

两个互质的数a,b，不能凑出来的最大值为a\*b-a-b

还有一个结论，裴蜀定理：两个数a,b能凑出来的数一定是gcd(a,b)的倍数

然后，对于这道题，如果这n个数的gcd不为1，说明有无数个数他是凑不出来的，因为他能够凑出来的一定是所有数的gcd的倍数，不是gcd的倍数的数是凑不出来的

如果gcd为1，那么这n个数不能凑出来的数的个数有上限，我们要求的就是这个上限

因此去考虑完全背包

设dp\[i\]\[j\]为前i个数，能不能凑出j

那么转移方程就是：dp\[i\]\[j\]=dp\[i-1\]\[j\]|dp\[i\]\[j-a\[i\]\]

还有一个问题，枚举j的上限是多少

考虑题目给的数据范围：1<=a\[i\]<=100，因此在1到100取最大的两个质数。它们不能凑出来的数的上限差不多在100左右，因此枚举j的上限也在100左右

最后跑一遍完全背包，统计一下就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e2+10;
    const int mxe=1e4+10;
    
    int n;
    int a[mxn],dp[mxn][mxe];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int d=a[1];
        for(int i=2;i<=n;i++) d=__gcd(d,a[i]);
        if(d!=1) cout<<"INF"<<'\n';
        else{
            dp[0][0]=1;
            for(int i=1;i<=n;i++){
                for(int j=0;j<=10000;j++){
                    dp[i][j]=dp[i-1][j];
                    if(j>=a[i]) dp[i][j]|=dp[i][j-a[i]];
                }
            }
            int ans=0;
            for(int j=0;j<=10000;j++){
                if(dp[n][j]==0) ans++;
            }
            cout<<ans<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[AcWing 1226. _ - AcWing]: https://www.acwing.com/activity/content/problem/content/1809/
[0f94025a58d2221aeddac3a4139f8933.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4e2e0d0c389b436490e723a19f2b52b6.png