HzuYZL

用户名：H2030819025

访问量：64030

签　名：

等　　级
排　　名	30
经　　验	14940
参赛次数	16
文章发表	25
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛真题-刷题统计
浏览：223

蓝桥杯2022年第十三届省赛真题-修剪灌木
浏览：312

蓝桥杯2018年第九届真题-日志统计(排序 + 双指针)
浏览：80

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

蓝桥杯2017年第八届真题-包子凑数 (背包DP)

　　作者: HzuYZL　　　　发表时间：2023-03-26 19:17:00 浏览：81　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-包子凑数

####解题思路
设有 N 个蒸笼，每个蒸笼能装 $$A_1, A_2,\dots, A_N$$ 个包子。
1.当 $$gcd(A_1, A_2,\dots, A_N)!=1$$ 时，则都不互质，凑不出的数目有无限个。（都为偶数时，则所有奇数凑不出来）
[裴蜀定理](https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593):若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

2.因为 N <= 100，最大不能表示的数为 100 * 99 - 100 - 99 <= 1e4。
3.状态转移方程：前 i 个物品中选，总价值是否为 j 的物品。
$$f[i, j] = f[i - 1, j] | f[i - 1, j - A_i] | f[i - 1, j - 2A_i] | \dots $$
改变 j 项
$$f[i, j - A_i] = f[i - 1, j - A_i] | f[i - 1, j - 2A_i] | \dots$$
状态转移方程优化：$$f[i, j] = f[i - 1, j] | f[i, j - A_i]$$
4.可以看出状态转移方程第 i 行是由 i - 1行的 j 状态与 i 行的 $$j - A_i$$列状态得出,都是上一次的状态来更新，可以直接用一维来解决。
状态转移方程：$$f[j] |= f[j - A_i]$$

####参考代码
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10;
int f[N], v[N];
int n;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    cin >> n;
    
    int d = 0;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &v[i]);
        d = gcd(d, v[i]);
    }
    
    if (d != 1)
    {
        puts("INF");
        return 0;
    }
    
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= N; j ++ )
            f[j] |= f[j - v[i]];
            
    int res = 0;
    for (int i = 1; i <= N; i ++ )
        if (!f[i])
            res ++ ;
    
    cout << res;
    
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuYZL

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

统计字符（C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-公约公倍（C语言代码）

简单的a+b （C语言代码）

蓝桥杯2017年第八届真题-包子凑数 (背包DP)

评论区

精彩推荐

wu-淘淘的名单（C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

幸运数（C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-等差数列（C语言代码）

统计立方数（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

计算质因子（Java代码）

HzuYZL

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

统计字符 （C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

简单的a+b （C语言代码）

蓝桥杯2017年第八届真题-包子凑数 (背包DP)

评论区

精彩推荐

wu-淘淘的名单 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

幸运数 （C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-等差数列 （C语言代码）

统计立方数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

计算质因子 （Java代码）

统计字符（C语言描述运用ctype.h）

C二级辅导-公约公倍（C语言代码）

　　评论区

wu-淘淘的名单（C++代码）

幸运数（C++代码）

C二级辅导-等差数列（C语言代码）

统计立方数（C语言代码）

计算质因子（Java代码）