题目概述

CF GYM103049A

解题报告

物品体积小，背包容量大的题，我们可以采用大范围贪心，小范围DP的办法。

当询问的背包容量超过 $V$ 时，我们选取性价比最低（ $a_i\over i$ 最小）的物品，直到背包容量降低到比 $V$ 的小的 $K$，此时直接通过DP得出答案 $f_K$ 。

注意，这道题在容量 $\le n$ 时不允许拆分，因此先枚举物品，再枚举容量的写法是错误的，应该先枚举体积，再枚举物品。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100,maxv=10000000;
 
int n,te,V,c[maxn+5];LL f[maxv+5],ans;
 
int main(){
    scanf("%d%d",&n,&te);V=maxv;
    for (int i=1;i<=V;i++) f[i]=9e18;f[0]=0;
    for (int i=1;i<=n;i++) scanf("%d",&c[i]),f[i]=c[i];
    for (int j=n+1;j<=V;j++)
        for (int i=1;i<=n;i++)
            if (f[j-i]+c[i]<f[j]) f[j]=f[j-i]+c[i];
    for (int t=1,x,k;t<=te;t++){
        scanf("%d",&x);LL ans=9e18;
        if (x<=V) ans=f[x]; else
            for (int i=1;i<=n;i++){
                int k=(x-V+i-1)/i;
                ans=min(ans,(LL)k*c[i]+f[x-k*i]);
            }
        printf("%lld\n",ans);
    }
    return 0;
}