ZigZagK的博客
[贪心+DP]Codeforces GYM103049A【Atomic Energy】题解
2021年6月3日 19:26
查看标签

题目概述

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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!