“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。”
失忆的Eden总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给Eden出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden这样的一个问题：有n个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。
这下Eden 犯难了，不过Eden不希望自己被难住，你能帮帮他么？
第一行一个数n，表示有n个玩偶，玩偶从0开始编号
第二行开始后面的 n行，每行三个数 ai, bi, c i，分别表示买一个第i个玩偶需
要的价钱，获得的价值以及第i个玩偶的限购次数。
接下来的一行为q，表示询问次数。
接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）
输出q行，第i行输出对于第 i个询问的答案。
一共五种玩偶，分别的价钱价值和限购次数为 (2,3,4)， (1,2,1)， (4,1,2)， (2,1,1)，(3,2,3)。五个询问，以第一个询问为例。第一个询问表示的是去掉编号为1的玩偶，且拥有的钱数为10时可以获得的最大价值，则此时剩余玩偶为(2,3,4)，(4,1,2)，(2,1,1)，(3,2,3)，若把编号为0的玩偶买4个（即全买了），然后编号为3的玩偶买一个，则刚好把10元全部花完，且总价值为13。可以证明没有更优的方案了。注意买某种玩偶不一定要买光。
100% 数据满足1 ≤ n ≤ 1000, 1 ≤ q ≤ 3*105 , 1 ≤ ai、bi、c i ≤ 100, 0 ≤ d i < n, 0 ≤ei ≤ 1000。
这题分明记得大爷讲过一次类似的问题，然而已经忘光了。
看到好多前辈都是奇妙的搞法，说数据很水可以卡过去（事实上理论复杂度很高的算法跑的飞起）。
最后从MG队长那里学来了CDQ分治的做法，时间复杂度是$O(NMlogN)$，应该是非常优秀的。
solve(l,r)表示处理区间[l,r]之内的所有问题。
solve(l,mid)时，区间[mid+1,r]内的物品都可以选取，所以先把[mid+1,r]加入背包再递归。
solve(mid+1,r)时，区间[l,mid]内的物品都可以选取，所以先把[l,mid]加入背包再递归。
做多重背包的时候，最好用单调队列把复杂度优化到$O(M)$（加入一种物品的复杂度）。这个没写过，所以先去HDU找了道模板题，YY了一发单调对列。
1 #include <cstdio> 2 3 template <class T> 4 __inline T max(const T &a, const T &b) 5 { 6 return a > b ? a : b; 7 } 8 9 template <class T> 10 __inline T min(const T &a, const T &b) 11 { 12 return a < b ? a : b; 13 } 14 15 template <class T> 16 __inline T read(T &x) 17 { 18 static char c; 19 20 x = 0, c = getchar(); 21 while (c < 48)c = getchar(); 22 while (c > 47)x = x*10 + c - 48, c = getchar(); 23 24 return x; 25 } 26 27 const int siz = 105; 28 29 int cas, n, m, f[siz]; 30 31 struct data 32 { 33 int pos, val; 34 35 inline data(void) {}; 36 inline data(int a, int b) 37 : pos(a), val(b) {}; 38 }q[siz]; 39 40 signed main(void) 41 { 42 for (read(cas); cas--; ) 43 { 44 read(m); 45 read(n); 46 47 for (int i = 0; i <= m; ++i)f[i] = 0; 48 49 for (int i = 1, a, b, c; i <= n; ++i) 50 { 51 read(a), read(b), read(c); 52 53 for (int j = 0; j < a; ++j) 54 { 55 int l = 0, r = 0; 56 57 q[r++] = data(j, f[j]); 58 59 for (int k = j + a; k <= m; k += a) 60 { 61 while (l != r && q[l].pos + a*c < k)++l; 62 while (l != r && q[r - 1].val + b*(k - q[r - 1].pos)/a < f[k])--r; 63 64 q[r++] = data(k, f[k]); 65 66 f[k] = max(f[k], q[l].val + b*(k - q[l].pos)/a); 67 } 68 } 69 } 70 71 printf("%d\n", f[m]); 72 } 73 }
1 #include <cstdio> 2 #include <cstring> 3 4 template <class T> 5 __inline T max(const T &a, const T &b) 6 { 7 return a > b ? a : b; 8 } 9 10 template <class T> 11 __inline T min(const T &a, const T &b) 12 { 13 return a < b ? a : b; 14 } 15 16 template <class T> 17 __inline void read(T &x) 18 { 19 static char c; 20 21 x = 0, c = getchar(); 22 while (c < 48)c = getchar(); 23 while (c > 47)x = x*10 + c - 48, c = getchar(); 24 } 25 26 const int mxv = 1E3; 27 const int mxn = 1E3 + 5; 28 const int mxm = 3E5 + 5; 29 30 int N, M; 31 32 int A[mxn]; 33 int B[mxn]; 34 int C[mxn]; 35 36 int D[mxm]; 37 int E[mxm]; 38 int Q[mxm]; 39 40 int hd[mxn], to[mxm], nt[mxm]; 41 42 inline void add(int u, int v) 43 { 44 static int tot = 0; 45 46 nt[++tot] = hd[u]; 47 to[tot] = v; 48 hd[u] = tot; 49 } 50 51 int f[15][mxn]; 52 53 struct data 54 { 55 int pos, val; 56 57 inline data(void) {}; 58 inline data(int a, int b) 59 : pos(a), val(b) {}; 60 }; 61 62 inline void add(int a, int b, int c, int *d) 63 { 64 static data q[mxn]; 65 66 for (int i = 0; i < a; ++i) 67 { 68 int l = 0, r = 0; 69 70 q[r++] = data(i, d[i]); 71 72 for (int j = i + a; j <= mxv; j += a) 73 { 74 while (l != r && q[l].pos + a*c < j)++l; 75 while (l != r && q[r - 1].val + b*(j - q[r - 1].pos)/a < d[j])--r; 76 77 q[r++] = data(j, d[j]); 78 79 d[j] = max(d[j], q[l].val + b*(j - q[l].pos)/a); 80 } 81 } 82 } 83 84 void solve(int l, int r, int d) 85 { 86 if (l == r) 87 { 88 for (int i = hd[l]; i; i = nt[i]) 89 Q[to[i]] = f[d - 1][E[to[i]]]; 90 } 91 else 92 { 93 int mid = (l + r) >> 1; 94 95 memcpy(f[d], f[d - 1], sizeof(f[0])); 96 for (int i = mid + 1; i <= r; ++i) 97 add(A[i], B[i], C[i], f[d]); 98 solve(l, mid, d + 1); 99 100 memcpy(f[d], f[d - 1], sizeof(f[0])); 101 for (int i = l; i <= mid; ++i) 102 add(A[i], B[i], C[i], f[d]); 103 solve(mid + 1, r, d + 1); 104 } 105 } 106 107 signed main(void) 108 { 109 read(N); 110 111 for (int i = 1; i <= N; ++i) 112 { 113 read(A[i]); 114 read(B[i]); 115 read(C[i]); 116 } 117 118 read(M); 119 120 for (int i = 1; i <= M; ++i) 121 { 122 read(D[i]); 123 read(E[i]); 124 125 add(D[i] + 1, i); 126 } 127 128 solve(1, N, 1); 129 130 for (int i = 1; i <= M; ++i) 131 printf("%d\n", Q[i]); 132 }
@Author: YouSiki
BZOJ 3163: [Heoi2013]Eden的新背包问题
原文：http://www.cnblogs.com/yousiki/p/6414054.html
