完全背包桶优化

显然我们要搞完全背包了。拼出一个数需要的糖果数就是物品的花费，得到金币数就是物品的价值，总糖果数是背包的大小。这样想非常简单，代码也简单，这里就不贴了。

那么你直接写好交上去，就会 TLE $5$ 个点。看这优美的数据范围，我们就知道要优化了。
摆在我们面前的是两条路：

• 生成函数优化：
  你们真以为我会吗
• 想一个其它的优化方法。

显然后者符合实际。认真地瞪数据范围，我们发现拼出每一个数需要的糖果数都在 $[1,63]$ 以内。原因很简单，因为最多拼成一个数只需要 $63$ 个糖果（$888888888$）。既然有这么多花费相同的物品，我们当然只想要价值最高的那个呀。于是，物品个数就被压到了 $63$ 个。$O(nm)$ 的朴素背包在 $n=63,m=100000$ 的数据范围下可以安全跑过。

#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;
}

---

提示：多测不清空，爆零两行泪。