当前位置: 首页 > news >正文

11 ACwing 281 Coins 题解

Coins

题面

给定 N 种硬币,其中第 i 种硬币的面值为 \(A_i\),共有 \(C_i\) 个。

从中选出若干个硬币,把面值相加,若结果为 S,则称“面值 S 能被拼成”。

求 1∼M 之间能被拼成的面值有多少个。

\(1 \le N \le 100\)

\(1 \le M \le 10^5\)

\(1 \le A_i \le 10^5\)

\(1 \le C_i \le 1000\)

题解

这道题是个典型的多重背包题目,我们可以设 \(f(j)\) 表示考虑前 \(i\) 个硬币的情况下,\(j\) 这个面额能否被拼出来,如果暴力的将每个硬币拆分成 \(C_i\) 个硬币的话,时间复杂度为 \(O(M\sum C_i)\) ,是不能接受的

给出两种优化方案,第一种是二进制拆分法优化多重背包,时间复杂度为 \(O(M\sum \log C_i)\) ,第二种是单调队列优化多重背包,时间复杂度为 \(O(NM)\)

蓝书中还给了一种巧妙的解决方法(

对于一个面值 \(j\) ,如果它能够被拼成,那么有两种情况

  • 在不使用硬币 \(i\) 的就已经能够被拼成
  • 使用硬币 \(i\) ,在某一次枚举中 \(f(j - a_i) = 1\)

回忆完全背包的枚举过程,我们正序枚举,这样 \(f(j - a_i)\) 这个状态就有可能是用过 \(i\) 的,从而实现无限次使用的效果

但我们并不能让它无限次使用,而是要限制一个使用次数 \(C_i\) ,如果我们知道前面的状态 \(f(j - a_i)\) 最少用了几个 \(i\) ,那么我们也就能推出当前 \(j\) 要想被拼成,至少要用几个 \(i\)

于是我们可以用一个数组 \(used_j\) 表示要拼成 \(j\) ,至少需要用多少 \(i\)

那么就有转移 \(f(j) |= f(j - a_i),used(j) = used(j - a_i) + 1\)

时间复杂度为 \(O(NM)\)

code

二进制拆分优化多重背包

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 110, M = 1e5 + 10;int n, m;
int a[N], c[N], used[M];
int w[N * 10], tot;
bool f[M];void init () {tot = 0;for (int i = 1; i <= n; i++) {for (int j = 0; j <= 10; j++) {if (c[i] >= (1 << j)) {tot ++;w[tot] = (1 << j) * a[i];c[i] -= (1 << j);} else break;}if (c[i]) {tot ++;w[tot] = c[i] * a[i];}}
}int main () {while (cin >> n >> m && n && m) {for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)cin >> c[i];init ();f[0] = 1;for (int i = 1; i <= tot; i ++) {for (int j = m; j >= w[i]; j --) {f[j] |= f[j - w[i]];}}int ans = 0;for (int i = 1; i <= m; i ++) {ans += f[i];f[i] = 0;}cout << ans << endl;}return 0;
}

单调队列优化多重背包

//这个代码比妈二进制拆分还慢,卡半天没过 POJ
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <bitset>using namespace std;const int N = 110, M = 1e5 + 10;int n, m, w[N], c[N];
int q1[M], q2[N], h, t;
bool f[M];int main () {while (cin >> n >> m && n && m) {for (int i = 1; i <= n; i ++) {cin >> w[i];}for (int i = 1; i <= n; i ++) {cin >> c[i];}f[0] = 1;for (int i = 1; i <= n; i ++) {for (int j = 0; j < w[i]; j ++) {h = 1, t = 0;for (int k = j; k <= m; k += w[i]) {while (h <= t && q1[h] < k - w[i] * c[i]) h ++;if (f[k]) q1[++ t] = k, q2[t] = f[k];if (h <= t && q2[h]) f[k] = 1;}}}int ans = 0;for (int i = 1; i <= m; i ++) {ans += f[i];f[i] = 0;}cout << ans << '\n';}return 0;
}

巧妙的转化

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 110, M = 1e5 + 10;int n, m;
int a[N], c[N], used[M];
bool f[M];int main () {while (cin >> n >> m && n && m) {for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)cin >> c[i];f[0] = 1;for (int i = 1; i <= n; i ++) {for (int j = 0; j <= m; j ++) {used[j] = 0;}for (int j = a[i]; j <= m; j ++) {if (!f[j] && used[j - a[i]] < c[i]) {f[j] |= f[j - a[i]];used[j] = used[j - a[i]] + 1;}}}int ans = 0;for (int i = 1; i <= m; i ++) {ans += f[i];f[i] = 0;}cout << ans << endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=25022

相关文章:

  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理