正经题解|圣诞礼物

这题就是完全背包，但是有很多的数需要的火柴棍数量相同，用map择优加入其中即可。
代码：

#include <iostream>
#include <map>
#include <algorithm>
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2,"Ofast","inline")
#pragma GCC optimize(1,"Ofast","inline")
using namespace std;
const int N=1e5+5;
struct data{
	int w,v;
}num[N];
long long a[N];
map<int,int> vis;
int w[N],v[N],sw[10]={6,2,5,5,4,5,6,3,7,6},idx;
int main() {
	int T;
	scanf("%d",&T);
	while (T--) {
		int n,m;
		scanf("%d %d",&n,&m);
		idx=0;
		vis.clear();
		for (int i=1;i<=n;i++) {
			int x;
			scanf("%d",&x);
			w[i]=0;
			while (x>0) {
				w[i]+=sw[x%10];
				x/=10;
			}
		}
		for (int i=1;i<=n;i++) {
			scanf("%d",&v[i]);
			vis[w[i]]=max(vis[w[i]],v[i]);
		}
		
		for (int i=1;i<=m;i++) a[i]=0;
		for (auto i:vis) {
			num[++idx].w=i.first;
			num[idx].v=i.second;
		}
		for (int i=1;i<=idx;i++) {
			for (int j=num[i].w;j<=m;j++) {
				a[j]=max(a[j],a[j-num[i].w]+num[i].v);
			}
		}
		printf("%lld\n",a[m]);
	}
	return 0;
}

这题虽然很简单但是赛时想了好久才想出来，导致提交次数非常多