D. Make Them Equal---dp预处理+01背包

#include 
#include 
#include 
using namespace std;
const int N = 1010,M=1000010;
int cost[N];
int b[N],c[N];
int f[M];
void solve()
{
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=0;i<=k;i++)f[i]=0;
	for(int i=1;i<=n;i++)scanf("%d",b+i);
	for(int i=1;i<=n;i++)scanf("%d",c+i);
	
	for(int i=1;i<=n;i++)
	{
		for(int j=k;j>=cost[b[i]];j--)
		{
			f[j]=max(f[j],f[j-cost[b[i]]]+c[i]);
		}
	}
	printf("%dn",f[k]);
}

signed main()
{
	memset(cost,0x3f,sizeof cost);
	cost[1]=0;cost[2]=1;
	for(int i=1;i<=1000;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(i+i/j<=1000)
			cost[i+i/j]=min(cost[i+i/j],cost[i]+1);
		}
	}
    int T;
    scanf("%d",&T);
    while(T--)solve();
}