首页 > 其他分享 >牛客CSP-J 入门组 --- 货币系统(完全背包)

牛客CSP-J 入门组 --- 货币系统(完全背包)

时间:2022-12-14 22:15:19浏览次数:58  
标签:表示 背包 int 系统 --- 牛客 货币 CSP dp

链接:https://ac.nowcoder.com/acm/problem/21467
来源:牛客网

题目描述

在网友的国度中共有n种不同面额的货币,第i种货币的面额为a[i],你可以假设每一种货币都有无穷多张。为了方便,我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。
在一个完善的货币系统中,每一个非负整数的金额x 都应该可以被表示出,即对每一个非负整数x,都存在n个非负整数t[i] 满足a[i] x t[i] 的和为x。然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中,金额1,3就无法被表示出来。
两个货币系统(n,a)和(m,b)是等价的,当且仅当对于任意非负整数x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b),满足(m,b) 与原来的货币系统(n,a)等价,且m尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的m。

输入描述:

输入的第一行包含一个整数T,表示数据组数。接下来按照如下格式分别给出T组数据。
每组数据的第一行包含一个正整数n。接下来一行包含n个由空格隔开的正整数a[i]。

输出描述:

输出文件共T行, 对于每组数据, 输出一行一个正整数, 表示所有与(n, a)等价的货币系统(m, b)中, 最小的m。
示例1

输入

复制
2
4
3 19 10 6
5
11 29 13 19 17

输出

复制
2
5

说明

在第一组数据中,货币系统(2, [3,10])和给出的货币系统(n, a)等价,并可以验证不存在m < 2的等价的货币系统,因此答案为2。
在第二组数据中,可以验证不存在m < n的等价的货币系统,因此答案为5。

备注:

1 <= T <= 20, 1 <= n <= 100, 1 <= a[i] <= 25000

思路:将原系统复制成一个新系统,并删掉该系统中能由其他数表示的数(不含自身)。

状态转移方程:dp[i] : 第i个货币a[i]能否由其他数表示,取值0或1。

具体解法:将原数组从排序,设背包容量为最大的a[i]即a[n-1], 这样每次新增一个物品a[i],能考虑从a[i] 到 a[n-1] 容量的背包能否被表示

设想?这类题和哪一类背包有联系?完全背包(自问自答,=。=)思路中说了,找到能由其他数表示的数,如3 4 7,7 由 3和4 表示,将其删掉,新系统只有3和4,互不表示(qinfan),m = 2即为最小。找这个数的过程可以理解成凑一次背包的过程。

如何找,请你先别急(bushi),代码中我写了解本题的三大关键:

 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int T, n, ans;
int a[110];
int dp[25007];

void solve() {
    
    cin >> T;

    while (T --) {
        cin >> n;
        ans = n;  // m系统考虑的数  
        for (int i = 0; i < n; i ++) {
            cin >> a[i];
        }
        
        sort(a, a + n);
    /*
    小注:(好吧有点多,举了一组例子,简单模拟了一下,如果小主赶时间可以不看~)

      排序是本题最关键的地方!!!  

        dp[i] 表示i能否被系统表示,第二个for开始,j = a[i] 的那一刻 dp[j] = dp[j - a[i]] = dp[0] = 1 自己当然能表示自己

        但是让 ans减一 的操作在这之前,在第一个for内部的if语句中,无论如何第一次if判断的dp[a[i]] 一定是等于0的,(i靠前时,没有其他较小数表示a[i])

        如一组数 7 3 4  排了序 3 4 7, 进入if判断:dp[a[0]] = dp[3] 初始是为0的,第二个for执行后 

        dp[6] = dp[3] = dp[0] = 1, 前面这个等式是本题第二大关键,也是完全背包的真正核心:

        考虑第i件物品时,能将容量为maxNum的背包中所有当前容量为k*a[i] (k = 0 1 2 3 4 ...) 时的情况都筛一遍

        排完序后,dp[3] = 1, 考虑下一件物品 a[1] = 4时, dp[7] = dp[7 - 4] = dp[3] = 1 

        这样,在考虑后面更大的数a[2] = 7,时,在if判断时就能把它踢掉了,即dp[a[2]] == 1, ans--, continue

    */
int maxNum = a[n - 1]; memset(dp, 0, sizeof(dp)); dp[0] = 1; // 0 能被被表示, 也是完全背包类题目一般的初始化步骤 for (int i = 0; i < n; i ++) { if (dp[a[i]] == 1) { ans --; continue; } for (int j = a[i]; j <= maxNum; j ++) { dp[j] = dp[j] || dp[j - a[i]]; } } cout << ans << endl; } return; } int main() { solve(); return 0; }

----------------------------------------------------------   分   割   线 ----------------------------------------------------------

小Mo的题解写得不够好,有些思路如果有启发性那再好不过,如果小主你有更好的思路和方法,请随时评论,小Mo看到一定会回复滴~

标签:表示,背包,int,系统,---,牛客,货币,CSP,dp
From: https://www.cnblogs.com/yumomo/p/16983762.html

相关文章

  • flask-05
    一、并发编程操作系统发展史进程基础:操作系统上运行的程序,是资源分配的最小单位进程调度:时间片轮转法并发和并行同步,异步,阻塞,非阻塞python创建进程两种方式:类继......
  • Git提交代码报错husky > pre-commit
    在接触了Git版本控制之后,很长一段时间里就只使用commit、pull、push这三个命令,并没有进行深究。而早上在用commit代码提交前端代码的时候出现了报错信息husky>pre-commit......
  • 2021-2022年游记
    \(NOI2022\)结束了,最后因为差\(34pts\)导致\(Ag\)了,下面是对初三一年的总结。\(CSP-S\)\(2021\)开场\(2.5h\)写完了前三题,想了很久\(t4\),但感觉只能网络流,但不......
  • HDMI设计3--HDMI 1.4/2.0 Transmitter Subsystem IP
    Reference: https://china.xilinx.com/content/dam/xilinx/support/documentation/ip_documentation/v_hdmi_tx_ss/v3_2/pg235-v-hdmi-tx-ss.pdf 对于支持4K视频的HDMI......
  • 「SWTR-04」Lining up
    链接:https://www.luogu.com.cn/problem/P6212题目描述:有一个串,每个字符为\(A,B,?\)中的一个。\(?\)会是\(A,B\)中等概率随机的一个字符,若有一个点为\(A\),其后面的点为\(B......
  • spring1-小结
    packagecom.example.demospring1;importcom.example.demospring1.service.UserService;importorg.springframework.beans.factory.annotation.Autowired;importor......
  • 实验七-缓冲区溢出
    实验指导书内容一、实验简介缓冲区溢出是指程序试图向缓冲区写入超出预分配固定长度数据的情况。这一漏洞可以被恶意用户利用来改变程序的流控制,甚至执行代码的任意片段......
  • 2022-2023-1 20221404《Linux内核原理与分析》缓冲区溢出实验-实验报告
    缓冲区溢出漏洞实验相关实验图片,所经历错误见结尾,建议先看结尾注意问题希望有所帮助一、实验简介缓冲区溢出是指程序试图向缓冲区写入超出预分配固定长度数据的情况。......
  • 牛客CSP-S提高组赛前集训营2
    牛客CSP-S提高组赛前集训营2预估得分:100+100+40实际得分:65+80+40不开longlong见祖宗T1服务器需求https://ac.nowcoder.com/acm/contest/1101/A小多计划在接下来......
  • 牛客CSP-J入门组 --- 简单的烦恼
    链接:https://ac.nowcoder.com/acm/problem/25184来源:牛客网题目描述网易云音乐推出了定时关闭播放的功能,假设到了定时关闭播放的时间,当前这首歌......