题解

首先，我们无脑用完全背包做

#include <iostream>
#include <cstdio>
#include <memory.h> 
#include <algorithm>
using namespace std;
short tmp[100005];
int b[100005];
unsigned long long dp[100005];
int dir[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
short turn_(int n){//转换成糖果数
	if(0 <= n && n <= 9) return dir[n];
	return dir[n % 10] + turn_(n / 10);
}
unsigned long long solve(){
	memset(dp, 0, sizeof(dp));
	int n, m, x;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &x);
		tmp[i] = turn_(x);
	}
	for(int i = 1; i <= n; i++){
		scanf("%d", b + i);
	}
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= tmp[i]; j--){
			for(int k = 1; k * tmp[i] <= j; k++){//完全背包
				dp[j] = max(dp[j - tmp[i] * k] + b[i] * k, dp[j]);
			}
		}
	} 
	return dp[m];
}
int main(){
	int t;
	cin >> t;
	while(t--){
		cout << solve() << endl;
	}

	return 0;
}

会发现这时间复杂度至少也得有$O(nm)$了，对于100000的数据肯定会超时
所以我们得用特殊的方法做
抽屉原理知道吧，跟这个没多大关系至少给了我们一些思路
$a_i\le10^9$，即每个不超过十位数，那最多要的糖果就绝对不超过70
那这样重复的一大堆，我们只要找给的金币最大的就行了
这样就用凑零钱的方法就行了
C++解法

#include <iostream>
#include <cstdio>
#include <memory.h> 
#include <algorithm>
using namespace std;
int bucket[75];
short tmp[100005];
int b[100005];
unsigned long long dp[100005];
int dir[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
short turn_(int n){
	if(0 <= n && n <= 9) return dir[n];
	return dir[n % 10] + turn_(n / 10);
}
unsigned long long solve(){
	memset(bucket, 0, sizeof(bucket));//重置，避免串题
	memset(dp, 0, sizeof(dp));
	int n, m, x;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &x);
		tmp[i] = turn_(x);
	}
	for(int i = 1; i <= n; i++){
		scanf("%d", b + i);
		bucket[tmp[i]] = max(bucket[tmp[i]], b[i]);//更新所需糖果相同时，金币最大值
	}
	for(int i = 2; i <= m; i++){
		for(int j = 2; j <= 70; j++){//凑零钱dp
			if(i >= j) dp[i] = max(dp[i], dp[i - j] + bucket[j]);
		}
	}
	return dp[m];
}
int main(){
	int t;
	cin >> t;
	while(t--){
		cout << solve() << endl;
	}

	return 0;
}

Python解法

dir = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
def turn_(n):#转换
    if(0 <= n <= 9): return dir[n]
    return dir[n % 10] + turn_(n // 10)
def solve():
    bucket = 75 * [0]#初始化
    a = input().split()
    n = int(a[0])
    m = int(a[1])
    a = input().split()
    tmp = [turn_(int(i)) for i in a]
    a = input().split()
    b = [int(i) for i in a]
    for i in range(n):
        bucket[tmp[i]] = max(bucket[tmp[i]], b[i])#更新所需糖果相同时，金币最大值
    dp = (m + 1) * [0]#初始化dp
    for i in range(2, m + 1):
        for j in range(2, 71):
            if(i >= j):
                dp[i] = max(dp[i], dp[i - j] + bucket[j])#凑零钱dp
    return dp[m]

t = int(input())
for i in range(t):
    print(solve())
        

时间复杂度：$O(70n)$
不得不说Python真的慢，$C++24ms,Python1.6s$