• P1064 金明的预算方案


    -----------------------------

    链接:Miku

    ------------------------------

    此文不是正解,而且主要内容都在代码和注释上

    ------------------------------

    这是暴力分组背包做法

    ----------------------------

    对于每一个主件及其附件,我们的选择是有限的,而且这道题中说了最多两个附件,那么

    我们完全可以枚举每一种组合,然后组合成一件新的物品,并且属于同一个集合,然后对处理后的新物品们

    跑分组背包就行了

    ---------------------------

    #include<iostream>
    #include<cstdio>
    using namespace std;
    long long  n,m;
    long long  x,y,z;
    long long  num[7000];//存该类别物品出现数量
    long long  cnt;//统计类别数
    struct th{
        long long  w;
        long long  v;
        long long  l;
    } t[7000],ft[7000];//一开始的和最后的物品
    long long  le[7000];//类别
    long long  f;//用来存物品的指针
    long long  po[7000][7000];//记录一下每一类物品的每一件的的存储下标
    long long  fn;//计数
    long long  fnum[7000];//同num
    long long  dp[32010];
    void add(long long  w,long long  v,long long  l){
        fn++;
        ft[fn].l=l;
        ft[fn].v=v;
        ft[fn].w=w;
    }
    int main(){
        scanf("%lld%lld",&n,&m);
        for(long long  i=1;i<=m;++i){
            scanf("%lld%lld%lld",&x,&y,&z);
            if(z==0){
                y=x*y;
                cnt++;
                f++;//记录这个主件
                num[cnt]++;
                t[f].v=x;
                t[f].w=y;
                t[f].l=cnt;
                le[i]=cnt;
                po[cnt][1]=f;
            }else{
                y=x*y;
                f++;
                t[f].v=x;
                t[f].w=y;//记录这个附件
                t[f].l=le[z];
                num[le[z]]++;//统计
                po[le[z]][num[le[z]]]=f;//表示这一类的第num【le【z】】个物品的下标
            }
        }    for(long long  i=1;i<=cnt;++i){//数据很小,暴力合并
                if(num[i]==1){
                    add(t[po[i][1]].w,t[po[i][1]].v,i);
                }
                if(num[i]==2){
                    add(t[po[i][1]].w+t[po[i][2]].w,t[po[i][1]].v+t[po[i][2]].v,i);
                    add(t[po[i][1]].w,t[po[i][1]].v,i);
                }
                if(num[i]==3){
                    add(t[po[i][1]].w+t[po[i][2]].w,t[po[i][1]].v+t[po[i][2]].v,i);
                    add(t[po[i][1]].w,t[po[i][1]].v,i);
                    add(t[po[i][1]].w+t[po[i][3]].w,t[po[i][1]].v+t[po[i][3]].v,i);
                    add(t[po[i][1]].w+t[po[i][3]].w+t[po[i][2]].w,t[po[i][1]].v+t[po[i][3]].v+t[po[i][2]].v,i);
                    num[i]=4;//会变成总共四个
                }
        }
        long long  summ=0;//开始跑分组背包
            for(long long  i=1;i<=cnt;++i){
            summ+=num[i-1];
            for(long long  j=n;j>=0;--j){
                for(long long  k=1;k<=num[i];++k){
                    if(j>=ft[summ+k].v)
                    dp[j]=max(dp[j],dp[j-ft[summ+k].v]+ft[summ+k].w);
                }
            }
        }
        printf("%lld",dp[n]);//end
        return 0;
    }
    Ac
  • 相关阅读:
    【洛谷3527】[POI2011] MET-Meteors(树状数组+整体二分)
    【洛谷1580】yyy loves Easter_Egg I(字符串处理题)
    【BZOJ4866】[YNOI2017] 由乃的商场之旅(莫队)
    【BZOJ4810】[YNOI2017] 由乃的玉米田(莫队+bitset)
    【洛谷1494】[国家集训队] 小Z的袜子(莫队)
    【BZOJ3668】[NOI2014] 起床困难综合症(位运算思想)
    【BZOJ3720】Gty的妹子树(主席树+时间分块)
    【BZOJ2427】[HAOI2010] 软件安装(缩点+树形DP)
    【洛谷3648】[APIO2014] 序列分割(斜率优化DP)
    动态规划专题(五)——斜率优化DP
  • 原文地址:https://www.cnblogs.com/For-Miku/p/12219572.html
一二三 - 开发者的网上家园