cf526 C. Om Nom and Candies
2022/6/11 23:52:09
本文主要是介绍cf526 C. Om Nom and Candies,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
背包问题:两种物品各无限个,体积分别为 \(c_1,c_2\),价值分别为 \(v_1,v_2\),背包容积为 \(C\),求最大价值
范围 \([1,1e9]\)
思路:
枚举!怎么优化?
若某种物品的体积大于 \(\sqrt C\),直接枚举这种物品的数量,不超过 \(\sqrt C\) 次。
否则,不妨设 \(\frac{v_1}{c_1} \le \frac{v_2}{c_2}\)。设拿 \(x\) 个物品一,
若 \(x\ge c_2\),则不如把 \(c_2\) 个物品一换成 \(c_1\) 个物品二,这样价值 \(c_2v_1\le c_1v_2\),且体积不会改变:\(-c_2c_1+c_1c_2=0\)
综上,只用从 \(0\) 到 \(\sqrt C\) 枚举 \(x\)
ll C, v1, v2, c1, c2, lim = 4e4; void sol() { cin >> C >> v1 >> v2 >> c1 >> c2; ll ans = 0; for(ll x = 0; x <= min(C/c1, lim); x++) ans = max(ans, x*v1+(C-x*c1)/c2*v2); swap(c1, c2), swap(v1, v2); for(ll x = 0; x <= min(C/c1, lim); x++) ans = max(ans, x*v1+(C-x*c1)/c2*v2); cout << ans; }
这篇关于cf526 C. Om Nom and Candies的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验