LINK：Eden 的新背包问题
就是一个多重背包 每次去掉一个物品 询问钱数为w所能买到的最大值。
可以对于每次Q暴力dp 利用单调队列优化多重背包 这样复杂度是Qnm的。
发现过不了n==10的点。
仔细观察n==10的点 可以发现我们暴力枚举 某个物品不选之后的最大值即可。设状态f[i][j]表示第i个物品不选此时钱数为j的最大值。
求出这个复杂度是n^2m的 然后可以O(1)回答询问。
考虑正解 可以发现 对于01背包或者多重背包 去掉一个物品询问最大价值 动态直接去掉是不现实的。
考虑分治 分治到某个点上表示其他的都加入背包了 就当前点没有加入背包的最大值。
然后 对于分治的两边 暴力合并。可以发现这个合并是m^2的。
进一步的 可以发现 分治的复杂度极高 不如直接求出前后缀的背包和 然后进行合并。
怎么把合并的复杂度降下来是问题 类似于卷积不过这个是取max.
考虑每次询问 只询问w 而不是询问整个m 所以直接合并的复杂度为O(m).
复杂度为Qm。3e8 但是跑的飞快。
const int MAXN=1010;
int n,Q,m;
int f[MAXN][MAXN],g[MAXN][MAXN];
int q[MAXN],l,r;
struct wy{int w,c,v;}t[MAXN];
int main()
{
freopen("1.in","r",stdin);
get(n);m=1000;
rep(1,n,i)
{
int get(x),get(y),get(z);
t[i]=(wy){x,z,y};
}
rep(1,n,i)//前i个物品
{
for(int res=0;res<w(i);++res)
{
int ww=(m-res)/w(i);
l=r=1;q[1]=0;
f[i][res]=f[i-1][res];
rep(1,ww,j)
{
while(l<=r&&j-q[l]>c(i))++l;
int s=j*w(i)+res;
f[i][s]=max(f[i-1][s],f[i-1][q[l]*w(i)+res]+(j-q[l])*v(i));
while(l<=r&&f[i-1][s]>=f[i-1][q[r]*w(i)+res]+(j-q[r])*v(i))--r;
q[++r]=j;
}
}
}
fep(n,1,i)
{
for(int res=0;res<w(i);++res)
{
int ww=(m-res)/w(i);
l=r=1;q[1]=0;g[i][res]=g[i+1][res];
rep(1,ww,j)
{
while(l<=r&&j-q[l]>c(i))++l;
int s=j*w(i)+res;
g[i][s]=max(g[i+1][s],g[i+1][q[l]*w(i)+res]+(j-q[l])*v(i));
while(l<=r&&g[i+1][s]>=g[i+1][q[r]*w(i)+res]+(j-q[r])*v(i))--r;
q[++r]=j;
}
}
}
get(Q);
rep(1,Q,i)
{
int x,w;
get(x)+1;get(w);
int ans=0;
rep(0,w,j)ans=max(ans,f[x-1][j]+g[x+1][w-j]);
put(ans);
}
return 0;
}