如果是裸的多重背包就非常简单了。。。
用f[i]表示用了cost为i的时候的最大价值
所以我们二分某一段[l, r]之间的物品不使用，剩下的都使用的最大值，这时的f[]数组可以由之前的f[]数组得到。。。
所以只要记录log(n)的f[]数组即可。。。
1 /************************************************************** 2 Problem: 3163 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:468 ms 7 Memory:8512 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 using namespace std; 15 const int N = 1005; 16 const int Cnt_q = 3e5 + 5; 17 const int Maxlen = N * 15 + Cnt_q * 10; 18 19 struct query { 20 int del, money, id; 21 query(){} 22 query(int _d, int _m, int _i) : del(_d), money(_m), id(_i) {} 23 24 inline bool operator < (const query &q) const { 25 return del < q.del; 26 } 27 } q[Cnt_q]; 28 29 int n, mxj, now; 30 int c[N], v[N], t[N]; 31 int ans[Cnt_q]; 32 int f[15][1005]; 33 34 char buf[Maxlen], *C = buf; 35 int Len; 36 37 inline int read() { 38 int x = 0; 39 while (*C < '0' || '9' < *C) ++C; 40 while ('0' <= *C && *C <= '9') 41 x = x * 10 + *C - '0', ++C; 42 return x; 43 } 44 45 void calc(int l, int r, int dep) { 46 int i, j, k, tot; 47 memcpy(f[dep], f[dep - 1], sizeof(f[dep])); 48 for (i = l; i <= r; ++i) { 49 tot = t[i]; 50 for (k = 1; k <= tot; k <<= 1) { 51 for (j = mxj; j >= c[i] * k; --j) 52 f[dep][j] = max(f[dep][j], f[dep][j - c[i] * k] + v[i] * k); 53 tot -= k; 54 } 55 if (!tot) continue; 56 k = tot; 57 for (j = mxj; j >= c[i] * k; --j) 58 f[dep][j] = max(f[dep][j], f[dep][j - c[i] * k] + v[i] * k); 59 } 60 } 61 62 #define mid (l + r >> 1) 63 void work(int l, int r, int dep) { 64 if (l == r) { 65 for (; q[now].del == l; ++now) 66 ans[q[now].id] = f[dep - 1][q[now].money]; 67 return; 68 } 69 calc(mid + 1, r, dep); 70 work(l, mid, dep + 1); 71 calc(l, mid, dep); 72 work(mid + 1, r, dep + 1); 73 } 74 #undef mid 75 76 int main() { 77 Len = fread(C, 1, Maxlen, stdin); 78 buf[Len] = ' '; 79 int i, x, y, Q; 80 n = read(); 81 for (i = 1; i <= n; ++i) 82 c[i] = read(), v[i] = read(), t[i] = read(); 83 Q = read(); 84 for (i = 1; i <= Q; ++i) { 85 x = read(), y = read(); 86 q[i] = query(x + 1, y, i); 87 mxj = max(mxj, y); 88 } 89 sort(q + 1, q + Q + 1), now = 1; 90 work(1, n, 1); 91 for (i = 1; i <= Q; ++i) 92 printf("%d ", ans[i]); 93 return 0; 94 }