包子凑数【蓝桥杯】/完全背包

包子凑数

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

完全背包

完全背包问题和01背包的区别就是,完全背包问题每一个物品能取无限次。
思路:当n个数的最大公约数不为1,即不互质时,有无限多个凑不出来的,即n个数都可以表示成kn,k为常数且不为1。当n个数的最大公约数为1,到了某个数之后就全都可以凑出来。
根据本题的数据,可以直接遍历到10010就行

#include<iostream>
using namespace std;
//dp[i]表示i这个数可不可以被凑出来
int dp[10010];
//欧几里得算法求最大公约数
int gcd(int a,int b)
{
    return (b==0)?a:gcd(b,a%b);
}
int main()
{
    int n;
    cin>>n;
    int a[n],g;
    for(int i=0;i<n;i++) 
    {
        cin>>a[i];
        if(i==0) g=a[i];
        else g=gcd(g,a[i]);
    }
    if(g!=1)
    {
        cout<<"INF"<<endl;
        return 0;
    }
    dp[0]=1;
    //完全背包
    for(int i=0;i<n;i++)
    {
        for(int j=a[i];j<10010;j++)
        {
            dp[j]=max(dp[j],dp[j-a[i]]);
        }
    }
    int ans=0;
    for(int i=0;i<10010;i++)
    {
        if(!dp[i]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519710.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

DFS序列

什么是DFS序 DFS序是指对一棵树进行DFS时&#xff0c;每个节点被访问到的顺序。DFS序分成两个部分&#xff1a;进入该节点的顺序和退出该节点的顺序。 如何求DFS序 对于DFS中当前节点 1&#xff1a;计数 2&#xff1a;进入当前节点的顺序等于当前计数 3&#xff1a;想所有…

达梦使用disql登录数据库显示“未连接”

基础环境 操作系统&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本&#xff1a;DM Database Server 64 V8 架构&#xff1a;单实例问题&#xff1a;达梦数据库在使用disql登录时&#xff0c;显示“未连接”。 指定了IP和端口号还是连接异常。 […

淘宝扭蛋机小程序源码搭建:打造专属电商娱乐新平台

在数字化浪潮的推动下&#xff0c;电商平台不断创新&#xff0c;以满足消费者日益多样化的需求。淘宝扭蛋机小程序作为一种创新的电商娱乐形式&#xff0c;受到了广大用户的热烈追捧。为了满足市场需求&#xff0c;许多企业和开发者开始关注淘宝扭蛋机小程序的源码搭建&#xf…

SAP S/4HANA的常见部署方式

SAP S/4HANA是SAP面向企业数字化转型推出一代商务ERP 套件&#xff0c;与传统的SAP ERP系统相比&#xff0c;它基于内存计算和先进的数据处理技术&#xff0c;提供更快的数据处理速度、实时分析和更好的用户体验。SAP S/4HANA可以根据企业的需求以多种部署方式进行实施&#xf…

【零基础学数据结构】顺序表实现书籍存储

目录 书籍存储的实现规划 ​编辑 前置准备&#xff1a; 书籍结构体&#xff1a; 书籍展示的初始化和文件加载 书籍展示的销毁和文件保存 书籍展示的容量检查 书籍展示的尾插实现 书籍展示的书籍增加 书籍展示的书籍打印 书籍删除展示数据 书籍展示修改数据 在指定位置之前…

LogicFlow 在HTML中的引入与使用

LogicFlow 在HTML中的引入与使用 LogicFlow的引入与使用&#xff0c;相较于BPMNJS相对容易一些&#xff0c;更加灵活一些&#xff0c;但是扩展代码可能写得更多一些。 示例展示 使用方式 这个的使用方式就简单很多了&#xff0c;利用cdn把js下载下来&#xff0c;引入到HTML文…

Python爬虫-懂车帝新能源汽车近一年销量榜

前言 本文是该专栏的第24篇,后面会持续分享python爬虫干货知识,记得关注。 笔者在本专栏之前,有详细介绍以“懂车帝平台的新能源汽车销量榜单”为例,获取各车型的销量排行榜单数据。而本文,笔者将单独详细来介绍如何获取“近一年的新能源汽车销量榜单”数据。 具体实现思…

信创(统信)系统上的软件安装及软件使用手册

一.各软件的安装文档 1.达梦数据库在统信系统上的安装 官方手册:https://eco.dameng.com/document/dm/zh-cn/start/install-dm-linux-prepare.html 1.1下载安装包 官网:https://www.dameng.com/list_103.html 点击”服务与合作”--> “下载中心” 这里选择对应的cpu和操作…

#include<初见c语言之字符函数和字符串函数>

目录 一、字符分类函数 二、字符转换函数 三、strlen的使⽤和模拟实现 1.strlen使用 2.strlen函数的模拟实现 四、 strcpy的使⽤和模拟实现 1.strcpy使用 2.strcpy函数的模拟实现 五、strcat的使用和模拟实现 1.strcat的使用 2.strcat的模拟实现 六、strcmp的使用…

【HTML】CSS样式(二)

上一篇我们学习了CSS基本样式和选择器&#xff0c;相信大家对于样式的使用有了初步认知。 本篇我们继续来学习CSS中的扩展选择器及CSS继承性&#xff0c;如何使用这些扩展选择器更好的帮助我们美化页面。 下一篇我们将会学习CSS中常用的属性。 喜欢的 【点赞】【关注】【收藏】…

214基于matlab的交互多模算法(IMM)机动目标跟踪算法

基于matlab的交互多模算法&#xff08;IMM&#xff09;机动目标跟踪算法&#xff0c;完整的15页文档论文。根据二维空间内目标作匀速直线运动和匀速圆周运动的特点&#xff0c;在建立目标运动模型和观测模型的基础上采用基于交互多模算法&#xff08;IMM&#xff09;的卡尔曼滤…

MySQL 50 道查询题汇总,足以巩固大部分查询(附带数据准备SQL、题型分析、演示、50道题的完整SQL)

目录 MySQL 50 道查询题&#xff0c;足以巩固大部分查询数据准备&#xff1a;创建表sql添加表数据sql 50道查询题目汇总01 - 05 题&#xff1a;1、查询 “01” 语文成绩比 “02” 数学成绩高的学生的信息及课程分数2、查询 "01语文课程"比"02数学课程"成绩…

ARM架构学习笔记2-汇编

RISC是精简指令集计算机&#xff08;RISC:Reduced Instruction Set Computing&#xff09; ARM汇编概述 一开始&#xff0c;ARM公司发布两类指令集&#xff1a; ① ARM指令集&#xff0c;这是32位的&#xff0c;每条指令占据32位&#xff0c;高效&#xff0c;但是太占空间 2…

0基础学习Mybatis系列数据库操作框架——自定义类型处理器

大纲 Java模型类定义类型处理器配置文件和类型绑定和字段绑定resultMap中绑定 Mapper代码测试类型对应关系表总结参考资料 我们有时候会在数据库中放入一个扩展字段&#xff0c;用于保存在表设计时尚未考虑到的、未来会加入的一些信息。这个字段我们一般使用字符串存储&#xf…

短视频素材高清无水印购买要多少钱?

大家好&#xff01;在制作短视频时&#xff0c;找到短视频素材高清无水印是非常重要的。那么&#xff0c;短视频素材高清无水印在哪里找呢&#xff1f;今天&#xff0c;我要给大家推荐六个主流的视频素材分享网站&#xff0c;帮助你轻松获取高质量的短视频素材高清无水印&#…

C++读取.bin二进制文件

C读取.bin二进制文件 在C中&#xff0c;可以使用文件输入/输出流来进行二进制文件的读写操作&#xff0c;方便数据的保存和读写。 //C读取bin二进制文件 int read_bin() {std::ifstream file("data_100.bin", std::ios::in | std::ios::binary);if (file) {// 按照…

Hive初始化元数据库(默认是derby数据库)时候出现缺少方法的错误com.google.common.base.Preconditions

错误的出现&#xff1a; 下载好hive后&#xff0c;初始化元数据库&#xff08;使用内置derby数据测试&#xff09;&#xff0c;出现报错 初始化hive元数据&#xff1a;schematool -dbType derby -initSchema 这个原因是与 Hive 和 Hadoop 版本的 Guava 版本不一样导致的。 解决…

SpringBoot+ECharts+Html 字符云/词云案例详解

1. 技术点 SpringBoot、MyBatis、thymeleaf、MySQL、ECharts 等 2. 准备条件 在mysql中创建数据库echartsdb&#xff0c;数据库中创建表t_comment表&#xff0c;表中设置两个字段word与count&#xff0c;添加表中的数据。如&#xff1a;附件中的 echartsdb.sql 3. SpringBoot…

webrtcP2P通话流程

文章目录 webrtcP2P通话流程webrtc多对多 mesh方案webrtc多对多 mcu方案webrtc多对多 sfu方案webrtc案例测试getUserMediagetUserMedia基础示例-打开摄像头getUserMedia canvas - 截图 打开共享屏幕 webrtcP2P通话流程 在这里&#xff0c;stun服务器包括stun服务和turn转发服…

Aurora8b10b(1)IP核介绍并基于IP核进行设计

文章目录 前言一、IP核设置二、基于IP核进行设计2.1、设计框图2.2、aurora_8b10b_0模块2.3、aurora_8b10b_0_CLOCK_MODULE2.4、aurora_8b10b_0_SUPPORT_RESET_LOGIC2.5、aurora8b10b_channel模块2.6、IBUFDS_GTE2模块2.7、aurora_8b10b_0_gt_common_wrapper模块2.8、aurora8b10…