题解 P1782 【旅行商的背包】

单调队列+玄学快读（否则T2-4个点） 1572ms 关于玄学快读的事参考[玄学快读](https://www.luogu.org/blog/CreeperLKF/FastRead) 然后我们知道标准的多重背包的dp转移方程为 ``` dp[i][j] = max{dp[i - 1][j - k * v[i]] + k * w[i]} ``` 然而你可以发现需要求最大值的对象有不少是重复的 于是我们设 ``` v = v[i]，a = j / v，b = j % v ``` 然后有 ``` dp[i][j] = max{dp[i - 1][b + k * v] - k * w[i]} + a * w[i] ``` 于是我们的max从 ``` dp[i - 1][j0] (j0 in b, b + v, b + 2v, ..., j) ``` 出来，然后这一部分我们用单调队列维护一下即可 AC代码如下 注意卡常：快读+手写队列 ``` #include <cstdio> #include <fcntl.h> #include <unistd.h> #include <sys/mman.h> using namespace std; #define MAXN 10005 #define Finline __inline__ __attribute__ ((always_inline)) char *pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0); inline int read(){ int num = 0; char c, sf = 1; while ((c = *pc++) < 45); if(c == '-') c = *pc++, sf = -1; while (num = num * 10 + c - 48, (c = *pc++) >= 48); return num * sf; } Finline void upmax(int &a, const int &b){ if(a < b) a = b; } int dp[MAXN], num[MAXN]; struct Q{ int s, t; int q[MAXN]; Q(){ s = 1 , t = 0; } Finline void clear(){ s = 1, t = 0; } Finline bool empty(){ return s > t; } Finline int front(){ return q[s]; } Finline int back(){ return q[t]; } Finline void pop_front(){ s++; } Finline void pop_back(){ t--; } Finline void push(int tar){ q[++t] = tar; } }q; int main(){ int n = read(), m = read(), c = read(), v, w, d, i, j, k, tmp1, tmp2, tmp3; for(i = 1; i <= n; ++i){ v = read(), w = read(), d = read(); for(j = 0; j < v; ++j){ for(k = 0, q.clear(); (tmp1 = k * v + j) <= c; ++k){ tmp3 = k * w; tmp2 = dp[tmp1] - tmp3; while(!q.empty() && tmp2 > num[q.t]) q.pop_back(); q.push(k), num[q.t] = tmp2; if(q.front() + d < k) q.pop_front(); dp[tmp1] = num[q.s] + tmp3; } } } for(i = 1; i <= m; ++i){ v = read(), w = read(), d = read(); for(j = c; j; --j){ for(k = 0; k <= j; k++){ upmax(dp[j], dp[j - k] + (v * k + w) * k + d); } } } printf("%d", dp[c]); return 0; } ```