题解 P1782 【旅行商的背包】
Creeper_LKF
2018-02-10 12:06:13
单调队列+玄学快读(否则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;
}
```