注册登录

Luogu P1782 旅行商的背包

gate

多重背包+01背包

以下是我的bug：

i<<=1写成i<<1...

价值和体积写反了...

一开始脑残了全写的多重背包，半红半蓝...后来反应过来，二次函数好像没法用二进制优化...

改完还是40'，然后注意到$ax^2+bx+c$，x是可以等于0的...

边界改了之后变成20'，发现不能用完全背包（我直接枚举占用体积，0的话会反复加），应该用01背包...

最后到了60'，剩下4个TLE，加了快读也没什么用，果断吸氧

代码如下（开O2的）

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
#define Darcy amour
using namespace std;

const int maxn = 1e6+10;
int n,m,v,x,y,z,cnt;
int w[maxn],c[maxn],f[maxn];

int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9') {
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x*f;
}

int main() {
    n = read(), m = read(), v = read();
    for(int i = 1; i <= n; i++) {
        x = read(), y = read(), z = read();
        z = min(z,v/x);
        for(int j = 1; j <= z; j <<= 1) {
            cnt++;
            c[cnt] = x*j;
            w[cnt] = y*j;
            z -= j;
        }
        if(z) {
            cnt++;
            c[cnt] = x*z;
            w[cnt] = y*z;
        }
    }
    for(int i = 1; i <= cnt; i++)
        for(int j = v; j >= c[i]; j--)
            f[j] = max(f[j],f[j-c[i]]+w[i]);
    for(int i = 1; i <= m; i++) {
        x = read(), y = read(), z = read();
        for(int j = v; j >= 0; j--)
            for(int k = 0; k <= j; k++)
                f[j] = max(f[j],f[j-k]+x*k*k+y*k+z);
    }
    printf("%d\n",f[v]);
    return 0;
}
知识兔View Code
计算机