题解 P1782 【旅行商的背包】

2018-02-10 12:06:13


单调队列+玄学快读(否则T2-4个点) 1572ms

关于玄学快读的事参考玄学快读

然后我们知道标准的多重背包的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;
}