洛谷P1858 多人背包 背包
正解:背包
解题报告:
,,,本来自以为,我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=300,V=5000+100,K=80; ll n,v,k,hv[N],val[N],ans; struct node{ll vl[K],sz;node(){sz=1;memset(vl,128,sizeof(vl));}}f[V]; //这里想注释下,,,这个是学到的一个小技巧,就是memset128相当于初始化负无穷w inline ll read() { register char ch=getchar();register ll x=0;register bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')ch=getchar(),y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),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=1,l2=1,l3=1;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,1,n)hv[i]=read(),val[i]=read();f[0].vl[1]=0; rp(i,1,n)my(j,v,hv[i])f[j]=mx(f[j],f[j-hv[i]],val[i]); rp(i,1,k)ans+=f[v].vl[i]; printf("%lld\n",ans); return 0; }