洛谷P1858 多人背包 多人背包板子题/多人背包学习笔记

时间：2022-06-24 07:28:15

正解:背包

解题报告:

,,,本来自以为,我dp学得还挺好的

然后今天一考发现都不会啊QAQ

连最基础的知识点都不清楚啊QAQ

所以就来写个题解嘛!

先放下板子题

其实我jio得,这题只要大概了解方法就不是很难鸭,,,毕竟是基础算法,还是比较好理解的QAQ

大概说下QwQ

就是开f[i],它是个一个长度为k的数组,表示的是重量为i时的前k优解(物品那一维显然可以滚掉不说

然后转移也很显然,就是f[i+val[j]]=max(f[i+val[j]],f[i])

注意一下就是这里的取max是指从这k*2个数中选前k大的,彼此之间没有捆绑关系的哈

还有一个是显然我们可以做到让f[i]表示的数组单调递减

这样我们取max的时候就可以归并排序做掉(事实上只是归并排序的思想QwQ

然后hl还分享了个用堆的方法

然而显然不够优秀而且很麻烦不写了,知道有这么个玩意儿可以直接用堆维护就好

(算了大概说一句,,,其实差不多,只是他的f[i]表示的就是个堆了,没了,,,合并起来还麻烦些QAQ

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define rp(i,x,y) for(register ll i=x;i<=y;++i)

#define my(i,x,y) for(register ll i=x;i>=y;--i)

const ll N=,V=+,K=;

ll n,v,k,hv[N],val[N],ans;

struct node{ll vl[K],sz;node(){sz=;memset(vl,,sizeof(vl));}}f[V];

//这里想注释下,,,这个是学到的一个小技巧,就是memset128相当于初始化负无穷w

inline ll read()

{

    register char ch=getchar();register ll x=;register bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

inline node mx(node x,node y,ll dat)

{

    node z;ll szz=min(x.sz+y.sz,k);ll l1=,l2=,l3=;z.sz=szz;

    while(l1<=x.sz && l2<=y.sz && l3<=szz)

    {

        if(x.vl[l1]>=y.vl[l2]+dat)z.vl[l3++]=x.vl[l1++];

        else z.vl[l3++]=y.vl[l2++]+dat;

    }

    while(l1<=x.sz && l3<=szz)z.vl[l3++]=x.vl[l1++];

    while(l2<=y.sz && l3<=szz)z.vl[l3++]=y.vl[l2++]+dat;

    return z;

}

int main()

{

    k=read();v=read();n=read();rp(i,,n)hv[i]=read(),val[i]=read();f[].vl[]=;

    rp(i,,n)my(j,v,hv[i])f[j]=mx(f[j],f[j-hv[i]],val[i]);

    rp(i,,k)ans+=f[v].vl[i];

    printf("%lld\n",ans);

    return ;

}

这儿是code!

相关文章