[CodeVS 3729]飞扬的小鸟
论如何把一个完全背包出的高大上……
这个题啊……细节特别多……
首先,不建议开滚动数组,细节处理就会疯。
然后呢……真的不太好说了……还是看代码吧(尽管代码还是有明显的滚动数组痕迹)。
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=10005,maxm=1005; const int INF=0x7f7f7f7f; #define REP(i,n) for(i=0;i<(n);i++) #define REP_B(i,n) for(i=1;i<=(n);i++) int GZ[maxn][2]; bool haveGZ[maxn]; int A[maxn][2]; int d[maxn][maxm]; int main(){ int n,m,k,temp; register int i,j,v,now,pre,ans=INF,cnt; scanf("%d%d%d",&n,&m,&k); cnt=k; REP(i,n){ scanf("%d%d",&A[i][0],&A[i][1]); } for(i=0;i<=n;i++){ GZ[i][0]=0; GZ[i][1]=m+1; } REP_B(i,k){ scanf("%d",&temp); haveGZ[temp]=true; scanf("%d%d",&GZ[temp][0],&GZ[temp][1]); } memset(d,0x7f,sizeof(d)); memset(d[0],0,sizeof(d[0])); d[0][0]=INF; REP_B(i,n){ now=i; pre=i-1; d[now][0]=INF; int& X=A[i-1][0]; int& Y=A[i-1][1]; REP_B(j,m){ if(j-X>0 && d[pre][j-X]<INF) d[now][j]=min(d[now][j],d[pre][j-X]+1); if(j-X>0 && d[now][j-X]<INF) d[now][j]=min(d[now][j],d[now][j-X]+1); if(j==m) for(v=j-X;v<=m;v++){ if(d[pre][v]<INF) d[now][j]=min(d[now][j],d[pre][v]+1); if(d[now][v]<INF) d[now][j]=min(d[now][j],d[now][v]+1); } } for(j=GZ[i][0]+1;j<GZ[i][1];j++){ if(j+Y<=m && d[pre][j+Y]<INF) d[now][j]=min(d[now][j],d[pre][j+Y]); } if(haveGZ[i]){ REP_B(j,GZ[i][0]) if(d[now][j]<INF){ d[now][j]=INF; } for(j=GZ[i][1];j<=m;j++) if(d[now][j]<INF){ d[now][j]=INF; } } } for(i=n;i>=1;i--){ for(j=m;j>=1;j--){ ans=min(ans,d[i][j]); } if(ans<INF) break; if(haveGZ[i]) cnt--; } if(cnt==k){ printf("1\n%d\n",ans); }else{ printf("0\n%d\n",cnt); } return 0; }
[CodeVS 3269]混合背包
哎……现在才敢说真正会背包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; }