[CodeVS 3269]混合背包
转载请注明出处:http://danihao123.is-programmer.com/
哎……现在才敢说真正会背包DP……
这个题可以分成三类问题分别处理,然后用一个一维数组一起递推。
0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高,可以考虑单调队列优化……然而窝太弱……不过还是用了
代码:
#include <cstdio> #include <algorithm> #include <queue> #include <deque> using namespace std; const int maxn=201,maxv=200001; struct DQueue{ deque<int> D; queue<int> Q; void push(int x){ Q.push(x); while(!D.empty() && x>D.back()) D.pop_back(); D.push_back(x); } int top(){ return D.front(); } void pop(){ if(D.front()==Q.front()) D.pop_front(); Q.pop(); } int size(){ return Q.size(); } void clear(){ while(!Q.empty()) Q.pop(); D.clear(); } }; int d[maxv]; int v; void pack(int V,int W,int c){ register int i,j,m; if(c==1){ for(i=v;i>=V;i--) d[i]=max(d[i],d[i-V]+W); }else{ if(c==-1){ for(i=V;i<=v;i++) d[i]=max(d[i],d[i-V]+W); }else{ c=min(c,v/V); for(i=0;i<V;i++){ m=(v-i)/V; DQueue Q; for(j=0;j<=m;j++){ if(Q.size()==c+1) Q.pop(); Q.push(d[j*V+i]-j*W); d[j*V+i]=Q.top()+j*W; } } } } } int main(){ register int i; int n,x,y,z; scanf("%d%d",&n,&v); for(i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); pack(x,y,z); } printf("%d\n",d[v]); return 0; }
Jul 03, 2023 11:38:09 AM
To offer specialised news coverage of current events in India, a group of professional writers has constituted itself under the name 12thmodelpaper. The publication of educational updates in the public interest is a passion of our team, which consists of professional 12thmodelpaper.in authors and citizen journalists with a wide range of journalism interests.In order to present the true image of current events,our reporting team intends to publish the Education & Recruitment Update for all age groups and provide inside coverage.