Luogu P4095 [HEOI2013] Eden的新背包问题
发布时间:2020-12-15 07:44:33 所属栏目:Java 来源:网络整理
导读:题目 求出从前往后的背包 (f_{i,j}) 和从后往前的背包 (F_{i,j}) 。 那么对于询问 ((d,e)) ,答案就是 (maxlimits_{i=0}^e f_{d-1,i}+F_{d+1,e-i}) 。 然后就是单调队列优化多重背包。 我们知道多重背包的转移 (f[i][j]=maxlimits_{k=0}^{min(c
题目 #include<bits/stdc++.h> #define mp make_pair #define P pair<int,int> #define fir first #define sec second using namespace std; const int N=1007,V=10007; int read(){int x;scanf("%d",&x);return x;} void max(int &a,int b){a=a>b? a:b;} int c[N],w[N],lim[N],d[N],e[N],f[N][V],F[N][V]; void cal(int *f,int x) { for(int i=0,j;i<c[x];++i) { deque<P>q{mp(0,f[i])}; for(j=1;j*c[x]+i<=10000;++j) { while(!q.empty()&&q.back().sec<=f[j*c[x]+i]-j*w[x]) q.pop_back(); q.push_back(mp(j,f[j*c[x]+i]-j*w[x])); while(!q.empty()&&q.front().fir<j-lim[x]) q.pop_front(); max(f[j*c[x]+i],q.front().sec+j*w[x]); } } } int main() { int i,d,e,n,q,ans; for(n=read(),i=1;i<=n;++i) c[i]=read(),w[i]=read(),lim[i]=read(); for(i=1;i<=n;++i) memcpy(f[i],f[i-1],sizeof f[i]),cal(f[i],i); for(i=n;i;--i) memcpy(F[i],F[i+1],sizeof F[i]),cal(F[i],i); for(q=read();q;--q) { d=read()+1,e=read(),ans=0; for(i=0;i<=e;++i) max(ans,f[d-1][i]+F[d+1][e-i]); printf("%dn",ans); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |