Codeforces 1132E(大数据多重背包)
2024-09-08 18:18:20
题意
给定背包容量$w$,体积分别为$1$到$8$的物体的数量求不超过背包容量的最大体积
思路
考虑将答案转化成$840 * x + y$的形式其中$840 = lcm(1-8), y < 840 * 8$,想法是对于选定的方案所有种类的物品都可以被表示成$840 * t_i + k_i$的形式,那么我们只用考虑每种物品凑不够$840$的那些物品的选取情况,如果能够知道这些选取情况下对应的能取到的最大的$840$份数就能得到答案。所以$dp[i][j]$表示已经考虑完前$i - 1$种物品后取出$j$重量的物品时能获得$840$的最大份数,答案显然为$max(840 * dp[9][i] + i)$当然这是有可能超过背包容量$w$的,所以还要和$w$作比较。
代码
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl using namespace std;
typedef long long LL; LL w, cnt[10], dp[10][840 * 8 + 5]; int main() {
scanf("%lld", &w);
for(int i = 1; i <= 8; i++) scanf("%lld", &cnt[i]);
memset(dp, -1, sizeof dp);
dp[1][0] = 0;
for(int i = 1; i <= 8; i++) {
for(int j = 0; j <= 840 * 8; j++) {
if(dp[i][j] == -1) continue;
LL t = min(cnt[i], 840LL / i);
for(int k = 0; k <= t; k++) {
dp[i + 1][j + k * i] = max(dp[i + 1][j + k * i], dp[i][j] + (cnt[i] - k) / (840 / i));
}
}
}
LL ans = 0;
for(int i = 0; i <= 840 * 8; i++) {
if(i > w || dp[9][i] == -1) continue;
ans = max(ans, i + min(dp[9][i], (w - i) / 840) * 840);
}
cout << ans;
}
最新文章
- sublime通用快捷键 汉化 安装 插件
- 返回值优化(RVO)
- 关于c#调用c编译器
- C语言中最常用的三种输入输出函数scanf()、printf()、getchar()和putchar()
- 异常处理:Sys.WebForms.PageRequestManagerParserErrorException:The message……
- mac下批量删除.svn文件
- EXTJS 4.2 资料 控件之textfield文本框加事件的用法
- ASP.NET 资料下载
- iOS修改截取图片不规范问题
- 20170422早会训话,ps:程序出现两次BUG,领导很生气
- 201521123078 《Java程序设计》第6周学习总结
- 【腾讯Bugly干货分享】Android 插件技术实战总结
- IDEA解决crtl+space与搜狗输入法冲突
- catch/finally中不应使用 writer.flush()
- kubernetes外部访问的几种方式
- New Reform---cf659E(dfs找环)
- 商铺项目(Logback配置与使用)
- 使用Amoeba实现mysql读写分离机制
- Android中9-Patch图片之理解
- java 简单工厂 工厂模式
热门文章
- 使用 GPG 签名提交
- 将xlsx列表文件转为md列表
- MongoDB6.0的安装「2023年」
- strapi系列-如何创建一个定时任务-Cron Jobs
- NG-ZORRO + angular-cli11 表格横纵向单元格合并,按需设置背景色,解决动态合并单元格动态colspan情况下,nzLeft固定列失效问题,也适用VUE,REACT
- 【分析笔记】DW7888 马达驱动芯片待机模式漏电流过高的问题
- 10月27日内容总结——hashlib加密模块和logging、subprocess模块
- drf-api接口、测试工具postman
- 重学SpringBoot. step5 再学SpringMVC
- Redis-03 数据格式和基础命令