[POI2005]BAN-Bank Notes
2024-09-08 08:43:36
[POI2005]BAN-Bank Notes
POI真好玩。。
如果没有记录方案的话就是一个简单的二进制或单调队列优化多重背包的问题。
但是非常难受的是要记录方案。
而且空间只给了\(64MB\),,令人不适。。。
可以记录状态\(to[i][j]\)表示从第i个物品转移到了j体积,这个在转移的时候记一下就行了
这个空间如果用二进制优化的话就需要\(nlog_bk\)的空间,大概是\(200×14×20000=56000000\)空间,必须开成\(bool\)数组,如果直接开\(int\)就\(MLE\)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=205,K=20005;
int n,a[N],f[K],b[N],tot,k,ans[N];
bool to[N<<4][K];
struct THINGS{
int vol,val,id;
}t[N<<4];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) {
for(int j=1;b[i]>=j;b[i]-=j,j<<=1)
t[++tot]=(THINGS){a[i]*j,j,i};
if(b[i]) t[++tot]=(THINGS){a[i]*b[i],b[i],i};
}
scanf("%d",&k);
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=tot;i++)
for(int j=k;j>=t[i].vol;j--)
if(f[j]>f[j-t[i].vol]+t[i].val) to[i][j]=1,f[j]=f[j-t[i].vol]+t[i].val;
printf("%d\n",f[k]);
int now=k,sum=f[k];
for(int i=tot;sum;) {
while(!to[i][now]) i--;
now-=t[i].vol;
ans[t[i].id]+=t[i].val;
sum-=t[i--].val;
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
最新文章
- python优先队列,队列和栈
- Kinect开发资源汇总
- js中typeof的使用方法
- [Xamarin.Android] Fragment Tips
- C++ 基本知识
- directsound 应用实例
- iframe与父页面中JS执行顺序控制
- 斯坦福IOS开发第五课(第一部分)
- MySQL 5.6.x 配置数据库主从复制
- 第五十五节,IO多路复用select模块加socket模块,伪多线并发
- spring boot访问数据库
- gdb命令中查看地址之x命令
- Python 文本和字节序列
- (转载)深入Java关键字this的用法的总结
- Docker入门之--基础知识
- 为什么要使用ThreadLocalRandom代替Random生成随机数
- dubbo-springboot入门级demo
- Docker最全教程——从理论到实战(二)
- 分享一个以前写的基于C#语言操作数据库的小框架
- Eureka 客户端 配置Eureka 爬坑
热门文章
- 2.5-冗余VLAN
- 设计模式实例(Lua)笔记之五(Bridge模式)
- mongodb mapreduce使用总结
- CSS3选择器(全)
- Kids Store - OpenCart 自适应主题模板 ABC-0022
- Codeforces Round #257 (Div. 2/B)/Codeforces450B_Jzzhu and Sequences
- HDU5567/BestCoder Round #63 (div.2) A sequence1 水
- C#中数据库备份还原 精简
- spring:使用<;prop>;标签为Java持久属性集注入值
- B1816 扑克牌 二分答案 + 贪心