题目链接
题意：You have an array of integers a of size n. Initially, all elements of the array are equal to 1. You can perform the following operation: choose two integers i (1≤i≤n) and x (x>0), and then increase the value of ai by ⌊ai/x⌋ (i.e. make ai=ai+⌊ai/x⌋).

After performing all operations, you will receive ci coins for all such i that ai=bi.

Your task is to determine the maximum number of coins that you can receive by performing no more than k operations.

Input：The first line contains a single integer t (1≤t≤100) — the number of test cases.

The first line of each test case contains two integers n and k (1≤n≤10^ 3;0≤k≤10^6) — the size of the array and the maximum number of operations, respectively.

The second line contains n integers b1,b2,…,bn (1≤bi≤10^3).

The third line contains n integers c1,c2,…,cn (1≤ci≤10^6).

The sum of n over all test cases does not exceed 10^3.

Output：For each test case, print one integer — the maximum number of coins that you can get by performing no more than k operations.

首先分析01背包，将k看成背包容量，共有n件物品，每件物品的价值为从1变成b[i]需要的最少操作次数。至此，01背包成型。

完全背包：作为预处理出现，我们需要求 从1变成b[i]需要的最少操作次数 可以将b[i]看成背包容量，因为b数组最大值为1000，所以我们只需要预处理从1到1000的最少操作数，将1000看成物品种类，物品价值就是1次操作。

代码如下：

#include <bits/stdc++.h>
//dfs 大法师
#define ll long long
using namespace std;
const int mod=20100403;
const int Inf=0x3f3f3f3f;
inline int read()
{int x=0,f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
int m1[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int m2[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
void Get_Time()
{time_t timep;time(&timep); //获取从1970至今过了多少秒，存入time_t类型的timepprintf("%s", ctime(&timep));//用ctime将秒数转化成字符串格式，输出：Thu Feb 28 14:14:17 2019
}
/*二分不会跳过正确答案*/
int b[1000005],c[1005],v[1005];
int dp[1000005];
void solve()
{int t;cin>>t;while(t--){int n,k,x;cin>>n>>k;//k=min(k,12*n)优化后memset(v,Inf,sizeof(v));v[1]=0;for(int i=1;i<=1000;i++)for(int j=1;j<=i;j++){v[i+i/j]=min(v[i+i/j],v[i]+1);}for(int a=1;a<=n;a++){cin>>x;b[a]=v[x];}for(int a=1;a<=n;a++)cin>>c[a];memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=k;j>=b[i];j--){dp[j]=max(dp[j],dp[j-b[i]]+c[i]);}}cout<<dp[k]<<endl;}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}

这样处理能ac，但是时间接近两秒，如果把限制时间改为1秒就会超时。所以还可以优化一下。

k是6次方的数值，意思就是b数组中的数，我们每个数可以操作1000次，不难发现，根本用不了1000次，那么最多需要多少次呢？

刚开始看别人的代码，他们将k优化为min（k，12*n），意思就是最多12次，这里为什么是12×n始终看不懂。其实我们已经求出了v数组，只需要看一看v数组里面的最大值就ok了！！！！！！！！！！！！！！