Description
“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。”
失忆的Eden总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给Eden出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden这样的一个问题：有n个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。
这下Eden 犯难了，不过Eden不希望自己被难住，你能帮帮他么？
Input
第一行一个数n，表示有n个玩偶，玩偶从0开始编号
第二行开始后面的 n行，每行三个数 ai, bi, c i，分别表示买一个第i个玩偶需
要的价钱，获得的价值以及第i个玩偶的限购次数。
接下来的一行为q，表示询问次数。
接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）
Output
输出q行，第i行输出对于第 i个询问的答案。
设[l,r]为[l,r]区间内不选的多重背包在总价钱[0,1000]的答案
从[l,r]可以O(log(c[i]))转移到[l+1,r],[l,r+1]
而询问为[a,a]
由[1,n]开始，[l,r]转移到[l,m]，[m+1,r]，递归下去回答询问
复杂度O(1000nlog(max(c[i]))logn)
#include<cstdio> #include<algorithm> #include<cstring> const int R=8000000; char buf[R],*ptr=buf-1; inline int _int(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x; } int n,q; int w[1024],v[1024],t[1024]; int f[1024]; struct Q{int w,mx,id;}qs[300010]; bool operator<(const Q&a,const Q&b){return a.w<b.w;} int qp=0; int ans[300010]; inline void ins(int x){ int s=t[x],_w,_v; for(int i=1;i<=s;i<<=1){ s-=i; _w=w[x]*i;_v=v[x]*i; for(int j=1000;j>=_w;--j){ int a=f[j-_w]+_v; if(a>f[j])f[j]=a; } } if(s){ _w=w[x]*s;_v=v[x]*s; for(int j=1000;j>=_w;--j){ int a=f[j-_w]+_v; if(a>f[j])f[j]=a; } } } void calc(int l,int r){ if(l==r){ while(qp<q&&qs[qp].w==l)ans[qs[qp].id]=f[qs[qp].mx],++qp; return; } int m=l+r>>1,now[1024]; memcpy(now,f,sizeof(f)); for(int i=r;i>m;i--)ins(i); calc(l,m); memcpy(f,now,sizeof(f)); for(int i=l;i<=m;i++)ins(i); calc(m+1,r); } int main(){ fread(buf,1,R-2,stdin); n=_int(); for(int i=0;i<n;i++)w[i]=_int(),v[i]=_int(),t[i]=_int(); q=_int(); for(int i=0;i<q;i++){ qs[i].w=_int(); qs[i].mx=_int(); qs[i].id=i; } std::sort(qs,qs+q); calc(0,n-1); for(int i=0;i<q;i++)printf("%d ",ans[i]); return 0; }