无限

[题解]洛谷P2347:砝码称重
原题链接:P2347 砝码称重好久没有做过这种毒瘤的dp水题了(CF114A可真是太毒瘤了可惜不是dp),当(显)...
扫描右侧二维码阅读全文
15
2019/02

[题解]洛谷P2347:砝码称重

原题链接:P2347 砝码称重


好久没有做过这种毒瘤的dp水题了(CF114A可真是太毒瘤了可惜不是dp),当(显)然也可能是我把它做毒瘤了。在题解区域看到了寥寥几笔的bitset题解(woc),%%%tql没有话说。

数据范围较小,时间极松,01背包可解,但是看着像多重背包就按多重背包打了,由于比较简单就直接贴代码如下:

#include<bits/stdc++.h>
using namespace std;
int x[1007];
int w[7]={1,2,3,5,10,20,0};
int a[7];
int f[1007];
int main(){
    memset(x,0,sizeof(x));
    memset(f,0,sizeof(f));
    for(int i=0;i<6;i++)scanf("%d",a+i);
    const int NUM_OF_ITEMS = 6;
    for(int i=0;i<NUM_OF_ITEMS;i++){
        int k=1;
        while(k<a[i]){
            int kw=k*w[i];
            for(int j=1007;j>=kw;j--){
                f[j]=max(f[j],f[j-kw]+kw);
                x[f[j]]++;
            }
            a[i]-=k;
            k<<=1;
        }
        int kw=a[i]*w[i];
        for(int j=1007;j>=kw;j--){
            f[j]=max(f[j],f[j-kw]+kw);
            x[f[j]]++;
        }
    }
    int ans=0;
    for(int i=1;i<1007;i++){
        if(x[i])ans++;
    }
    printf("Total=%d",ans);
    return 0;
}

NUM_OF_ITEMS没卵用,就是看着[heimu]牛逼[/heimu]方便易懂,过上十几天我自己未必看得懂一个6是啥意思,但是const一下就问题不大了。

数组开7不开6是因为6不是素数看着不舒服(什么坏习惯),1007也是这个原因。

for循环里面那个1007没const所以有点看不懂,附注一下:这是我虚拟的一个背包容量,根据题意来。

然后数组x是个桶,维护f数组的时候顺手把桶维护了,最后$O(N)$时间把桶统计一下就ok。

时间复杂度$O(\sum log a_{i})$,空间复杂度$O(N)$,其中$N$为砝码总重。

水一水就过去了 -> R16356314

最后修改:2019 年 02 月 15 日 06 : 50 PM

1 条评论

  1. 无限

    Note : 时间复杂度原本还应乘以N,但是本题N为常数。

发表评论