P8646 [蓝桥杯 2017 省 AB] 包子凑数

根据裴蜀定理可得INF的情况是所有数的最大公约数非1

而我们的完全背包的上限是多少呢?

设置为Σai即可，因为把每一个ai用上之后的集合，和ai可以重复使用的集合，只差了整数倍个ai，因此可达性是完全一致的，这里N<=100,ai<=100，所以我们把这个背包的上限设置为10000.

#include <bits/stdc++.h>
using namespace std;
int gcd(int m, int n)
{
    if(n)
    {
        return gcd(n, m % n);
    }
    else
    {
        return m;
    }
}//求gcd(m,n),常见的递归写法
const int MAXN = 105, MAX_DP = 100005;//又来定义
int n, a[MAXN], dp[MAX_DP], ans;
bool notCoprime(int *arr)//返回arr数组中所有数的最大公约数是否大于1
{
    int g = arr[0];
    for(int i = 1; i < n; i++)
    {
        g = gcd(g, arr[i]);
        if(g == 1)
        {
            return false;//如果g已经为1，不用再循环，直接返回
        }
    }
    return g > 1;
}//定义函数，运行更快
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }//输入
    if(notCoprime(a))//如果gcd({A_i})>1
    {
        printf("INF");
        return 0;//直接结束
    }
    dp[0] = 1;//注意0是被认为能被凑出的，否则所有数都凑不出来，循环检查时可以不用从0开始
    for(int i = 0; i < n; i++)
    {
        for(int j = a[i]; j < MAX_DP; j++)
        {
            dp[j] = max(dp[j], dp[j - a[i]]);//状态转移方程
        }
    }
    for(int i = 1; i < MAX_DP; i++)
    {
        if(!dp[i])
        {
            ans++;//如果dp[i]=0,多一个凑不出的数
        }
    }
    printf("%d", ans);//输出
    return 0;
}

还有大佬的剩余类最短路做法（可以更好的解释为什么那个完全背包的上限设置为Σai）

#include <queue>
#include <cstdio>
#include <cstring>
#define P pair<int, int>
using namespace std;
struct E
{
    int v, w, t;
} e[10050];
int n, c, z, a[150], d[150], h[150];
bool b[150];
priority_queue<P, vector<P>, greater<P>> q;
void A(int u, int v, int w)
{
    e[++c] = {v, w, h[u]};
    h[u] = c;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    for (int i = 0; i < a[1]; ++i)
        for (int j = 2; j <= n; ++j)
            A(i, (i + a[j]) % a[1], a[j]);
    memset(d, 0x3f, sizeof d);
    q.emplace(d[0] = 0, 0);
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (!b[u])
        {
            b[u] = 1;
            for (int i = h[u], v; i; i = e[i].t)
                if (d[v = e[i].v] > d[u] + e[i].w)
                    q.emplace(d[v] = d[u] + e[i].w, v);
        }
    }
    for (int i = 0; i < a[1]; ++i)
    {
        if (d[i] == 0x3f3f3f3f)
            return !puts("INF");
        z += d[i] / a[1];
    }
    printf("%d", z);
    return 0;
}