北大oj Coins

2024-06-18 00:52
文章标签 北大 oj coins

本文主要是介绍北大oj Coins,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem: 北大oj Coins

文章目录

  • 思路
  • 解题方法
  • 复杂度
  • Code

思路

题目要求我们找出所有可能组成的金额总数,给定一系列硬币面值和每种硬币的数量。我们使用动态规划来解决这个问题。关键在于如何处理每种硬币数量大于1的情况,这需要对余数进行分组,以便于在遍历时能够有效地更新状态。

解题方法

我们首先初始化一个布尔数组dp,其长度为最大目标金额m加上1。数组中的每个元素表示是否可以组成对应位置的金额。接下来,对于每种硬币,根据其数量的不同,采取不同的策略更新dp数组。如果硬币数量为1,则直接更新dp数组;如果硬币数量多且硬币总价值大于m,则可以视为无限数量的硬币;否则,需要根据余数进行分组更新。

复杂度

时间复杂度:

O ( n × m ) O(n×m) O(n×m),其中n是硬币种类数,m是目标金额。

空间复杂度:

O ( m ) O(m) O(m),主要取决于dp数组的大小。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static int MAXN = 110;static int MAXM = (int) (1e5 + 10);static int[] val = new int[MAXN];static int[] cnt = new int[MAXN];static boolean[] dp = new boolean[MAXM];static int n, m;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() != StreamTokenizer.TT_EOF) {n = (int) in.nval;in.nextToken();m = (int) in.nval;if (n != 0 || m != 0) {for (int i = 1; i <= n; i++) {in.nextToken();val[i] = (int) in.nval;}for (int i = 1; i <= n; i++) {in.nextToken();cnt[i] = (int) in.nval;}out.println(deal());}}out.flush();out.close();br.close();}private static int deal() {// TODO Auto-generated method stubArrays.fill(dp, 1, m + 1, false);dp[0] = true;for(int i = 1; i <= n; i++) {if(cnt[i] == 1) {for(int j = m ; j >= val[i]; j--) {if(dp[j - val[i]]) {dp[j] = true;}}} else if(val[i] * cnt[i] > m) {for(int j = val[i]; j <= m; j++) {if(dp[j - val[i]]) {dp[j] = true;}}} else {// 根据余数分组for (int mod = 0; mod < val[i]; mod++) {int trueCnt = 0;for (int j = m - mod, size = 0; j >= 0 && size <= cnt[i]; j -= val[i], size++) {trueCnt += dp[j] ? 1 : 0;}for (int j = m - mod, l = j - val[i] * (cnt[i] + 1); j >= 1; j -= val[i], l -= val[i]) {if (dp[j]) {trueCnt--;} else {if (trueCnt != 0) {dp[j] = true;}}if (l >= 0) {trueCnt += dp[l] ? 1 : 0;}}}}}int ans = 0;for(int i = 1; i <= m; i++) {if(dp[i]) {ans++;}}return ans;}}

这篇关于北大oj Coins的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070854

相关文章

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

本专栏栏目提供文章与程序复现思路,具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源程序擅长文章解读,论文与完整源程序,等方面的知识,电网论文源程序关注python

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N,从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

OJ-0905

题目 示例1: 输入:10 10 56 34 99 1 87 8 99 3 255 6 99 5 255 4 99 7 255 2 99 9 255 213 4输出:99 示例2: 输入:10 10 255 34 0 1 255 8 0 3 255 6 0 5 255 4 0 7 255 2 0 9 255 213 5输出:255 import java.util.

每日OJ_牛客_Emacs计算器(逆波兰表达式)

目录 牛客_Emacs计算器(逆波兰表达式) 解析代码 牛客_Emacs计算器(逆波兰表达式) Emacs计算器__牛客网 解析代码 逆波兰表达式(后缀表达式)求值,需要借助栈,思路: 循环输入,获取逆波兰表达式,然后进行以下补助,直到测试完所有的测试用例: 遇到数字字符串,将该数字字符串转化为数字然后入栈。遇到操作符时,从栈顶取两个数字,然后进行该运算符所对应运算

西北工业大学oj题-兔子生崽

题目描述: 兔子生崽问题。假设一对小兔的成熟期是一个月,即一个月可长成成兔,每对成兔每个月可以生一对小兔,一对新生的小兔从第二个月起就开始生兔子,试问从一对兔子开始繁殖,一年以后可有多少对兔子? 这道题目一眼看过去就是典型的递归问题,代码如下 public class RabbitReproduction {public static void main(String[] args) {in

文章解读与仿真程序复现思路——中国电机工程学报EI\CSCD\北大核心《考虑极端事件的电力系统惯量与一次调频备用联合规划配置方法》

本专栏栏目提供文章与程序复现思路,具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源程序擅长文章解读,论文与完整源程序,等方面的知识,电网论文源程序关注python

★ 算法OJ题 ★ 力扣209 - 长度最小的子数组

Ciallo~(∠・ω< )⌒☆ ~ 今天,简将和大家一起做一道滑动窗口算法题--长度最小的子数组~ 目录 一  题目 二  算法解析 解法⼀:暴力求解 解法二:滑动窗口 三  编写算法 一  题目 209. 长度最小的子数组 - 力扣(LeetCode) 二  算法解析 解法⼀:暴力求解 算法思路: 从前往后枚举数组中的任意⼀个元素,把它当成起始位置

OJ-0903

题目 示例1 输入:30 12 25 8 19输出:15 示例2 输入:10 12 25 8 19 8 6 4 17 19 20 30输出:-1 题解 import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main {public static

【负载均衡式在线OJ】Compile_server 模块

文章目录 程序源码compile_server整体思路编译(compile.hpp)运行模块编译运行模块编译运行服务 程序源码 https://gitee.com/not-a-stupid-child/online-judge compile_server 整体思路 这个服务要对oj_server 发送过来的代码进行编译和运行,最后把结果返回给oj_server。 所以我