/category/pk/ zh-CN Tue, 15 Nov 2016 08:21:00 +0800 Tue, 15 Nov 2016 08:21:00 +0800 /archives/74/ /archives/74/ Tue, 15 Nov 2016 08:21:00 +0800 admin ###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个询问的答案。 ###Sample Input 5 2 3 4 1 2 1 4 1 2 2 1 1 3 2 3 5 1 10 2 7 3 4 4 8 0 5 ###Sample Output 13 11 6 12 4 ###Solution 多重背包+分治背包 递归处理[l,r)，每次加入左半部分的点，处理右边，再加入右边，处理左边 时间复杂度$$O(n^2log^2n+q)$$ ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) struct _toy { int a,b,c; }toy[1000]; struct _qr { int w,ans,ne; }qr[300001]; int p[1000],n,q,f[11][1001]; inline void merge(int *s,int a,int b) { for(int i=1000;i>=a;i--) repr(s[i],max(s[i-1],s[i-a]+b)); } void solve(int l,int r,int d) { if(l+1==r) { for(int i=p[l];i;i=qr[i].ne) qr[i].ans=f[d][qr[i].w]; } else { int p=(l+r)>>1; memcpy(f[d+1],f[d],sizeof(f[d])); for(int i=l;i<p;i++) { int t=toy[i].c; for(int j=1;j<t;t-=j,j<<=1) merge(f[d+1],toy[i].a*j,toy[i].b*j); merge(f[d+1],toy[i].a*t,toy[i].b*t); } solve(p,r,d+1); memcpy(f[d+1],f[d],sizeof(f[d])); for(int i=p;i<r;i++) { int t=toy[i].c; for(int j=1;j<t;t-=j,j<<=1) merge(f[d+1],toy[i].a*j,toy[i].b*j); merge(f[d+1],toy[i].a*t,toy[i].b*t); } solve(l,p,d+1); } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d%d",&toy[i].a,&toy[i].b,&toy[i].c); scanf("%d",&q); for(int i=1;i<=q;i++) { int x; scanf("%d%d",&x,&qr[i].w); qr[i].ne=p[x]; p[x]=i; } solve(0,n,0); for(int i=1;i<=q;i++) printf("%d\n",qr[i].ans); } ``` ]]> 0 /archives/74/#comments /feed/archives/74/