完全背包桶优化
2024-06-22 14:17:07
发布于:上海
43阅读
0回复
0点赞
显然我们要搞完全背包了。拼出一个数需要的糖果数就是物品的花费,得到金币数就是物品的价值,总糖果数是背包的大小。这样想非常简单,代码也简单,这里就不贴了。
那么你直接写好交上去,就会 TLE 个点。看这优美的数据范围,我们就知道要优化了。
摆在我们面前的是两条路:
- 生成函数优化:
你们真以为我会吗 - 想一个其它的优化方法。
显然后者符合实际。认真地瞪数据范围,我们发现拼出每一个数需要的糖果数都在 以内。原因很简单,因为最多拼成一个数只需要 个糖果()。既然有这么多花费相同的物品,我们当然只想要价值最高的那个呀。于是,物品个数就被压到了 个。 的朴素背包在 的数据范围下可以安全跑过。
#include <cstdio>
#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>
using namespace std;
const int luck[10]={6,2,5,5,4,5,6,3,7,6};
inline int readl(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x+=luck[(ch^48)];
ch=getchar();
}
return x;
}
int a[100005],b[100005];
int buc[105];
int w[100005],c[100005];
long long f[100005];
int main(){
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++) a[i]=readl();
for(int i=1; i<=n; i++) cin>>b[i];
for(int i=1; i<=n; i++){
buc[a[i]]=max(buc[a[i]],b[i]);
}
n=100;
for(int i=1; i<=n; i++) w[i]=i,c[i]=buc[i];
for(int i=1; i<=n; i++){
for(int j=w[i]; j<=m; j++){
f[j] = max(f[j-w[i]]+c[i], f[j]);
}
}
cout << f[m] << endl;
for(int i=1; i<=m; i++) f[i]=0;
memset(buc,0,sizeof(buc));
}
return 0;
}
提示:多测不清空,爆零两行泪。
全部评论 1
好像不是,是
2024-06-22 来自 广东
0是 个糖拼的, 是 位数,,是 吧。
2024-06-22 来自 上海
0是十位数以内,极限是9个8
2024-06-22 来自 广东
0搞错了,抱歉,已修改 。
2024-06-22 来自 上海
0
有帮助,赞一个