解

expnoi · 2022-02-05 19:22:05 · 题解

按照题意，容易想到用01背包做。

可以把 n 看做物品的数量； k 看做物品的体积 v； c[i] 看做物品的价值；把 1 操作到 b[i] 的最少操作数量看做物体的题解 w[i] 。并用这些获得的信息来做01背包。

那么问题来了，如何求出把 1 操作到 b[i] 的最少操作数量呢？

我们可以递推求解。

我们设 f[i] 表示把 1 操作到 i 的最少操作数量。那么，根据题意的修改方式，我们可以得出以下代码：

memset(f,0x3f,sizeof(f));
f[1]=0;//初始化，1操作到1是0
for(int i=1;i<=1000;i++)
{
    for(int j=1;j<=i;j++)//即为除数x
    {
        f[i+i/j]=min(f[i+i/j],f[i]+1);//把i修改成i+i/j，更新答案
    }
}

那么，这样预处理出了结果。

下面是代码：

#include<bits/stdc++.h>
using namespace std;
int T,N,V,b[1001],w[1001],c[1001],f[2001],dp[1000001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i+i/j]=min(f[i+i/j],f[i]+1);
        }
    }
    cin>>T;
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        cin>>N>>V;
        for(int i=1;i<=N;i++)
        {
            cin>>b[i];
            w[i]=f[b[i]];
        }
        for(int i=1;i<=N;i++)
        {
            cin>>c[i];
        }
        for(int i=1;i<=N;i++)
        {
            for(int j=V;j>=w[i];j--)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
            }
        }
        cout<<dp[V]<<"\n";
    }
}