BZOJ 3163 Heoi2013 Eden的新背包問題 多重背包
來源：程序員人生 發(fā)布時間：2015-04-10 08:31:04 閱讀次數：3433次
題目大意：多重背包，屢次詢問某個物品不能選擇時以某個總價錢最多能取得多少價值
求問正解是啥QAQ
保護1個前綴多重背包和1個后綴多重背包
每次詢問時 枚舉前面選多少和后面選多少 暴力統(tǒng)計答案便可
時間復雜度O(n^2logn+nq) 這3E的復雜度竟然只跑了600sQAQ
正解究竟是啥QAQ
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1010
using namespace std;
int n,q;
int cost[M],value[M],limit[M];
int f[M][M],g[M][M],h[M][M];
int main()
{
int i,j,k,x,y;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d%d%d",&cost[i],&value[i],&limit[i]);
for(i=1;i<=n;i++)
{
int temp=limit[i];
for(j=0;j<=1000;j++)
f[i][j]=f[i⑴][j];
for(j=1;temp;j=min(j<<1,temp))
{
for(k=1000;k>=j*cost[i];k--)
f[i][k]=max(f[i][k],f[i][k-j*cost[i]]+j*value[i]);
temp-=j;
}
}
for(i=n;i;i--)
{
int temp=limit[i];
for(j=0;j<=1000;j++)
g[i][j]=g[i+1][j];
for(j=1;temp;j=min(j<<1,temp))
{
for(k=1000;k>=j*cost[i];k--)
g[i][k]=max(g[i][k],g[i][k-j*cost[i]]+j*value[i]);
temp-=j;
}
}
cin>>q;
for(i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);++x;
int ans=0;
for(j=0;j<=y;j++)
ans=max(ans,f[x⑴][j]+g[x+1][y-j]);
printf("%d
",ans);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
