P1833 樱花

题目

P1833 樱花

算法标签: 动态规划, 线性$dp$, 背包问题, 背包问题优化

思路

很明显的混合背包问题, 可以首先将完全背包问题转化为多重背包问题, 然后在多重背包问题基础上进行优化, 多重背包可以使用二进制拆分优化或者单调队列优化, 同时因为当前状态只与上一层状态有关, 可以使用滚动数组优化省掉一维空间

二进制优化代码

注意因为新拆分的物品数量要乘$\log P$, 否则空间不够

拆分物品时间复杂度$O(n\log P)$, $01$背包时间复杂度$O(n\log P)\times M$, 总的时间复杂度就是$O(n\log P\times M)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 1010, K = 8;

int n, m;
int v[N * K], w[N * K], cnt;
int f[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    char ch;
    int a, b, c, d;
    cin >> a >> ch >> b >> c >> ch >> d;
    m = 60 * (c - a) + d - b;

    cin >> n;

    for (int i = 1; i <= n; ++i) {
   
        int _v, _w, s;
        cin >> _v >> _w >> s;
        if (s == 0) s = m / _v;

        int k = 1;
        while (k <= s) {
   
            cnt++;
            v[cnt] = k * _v;
            w[cnt] = k * _w;
            s -= k;
            k <<= 1;
        }
        if (s > 0) {
   
            ++cnt;
            v[cnt] = s * _v;
            w[cnt] = s * _w;
        }
    }

    for (int i = 1; i <= cnt; ++i) {
   
        for (int j = m; j >= v[i]; --j) {
   
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << "\n";
    return 0;
}

单调队列优化代码

单调队列优化, 算法时间复杂度$O(NM)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 1010;

int n, m;
int v[N], w[N], s[N];
int f[M], g[M];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    char ch;
    int a, b, c, d;
    cin >> a >> ch >> b >> c >> ch >> d;
    m = (c - a) * 60 + d - b;

    cin >> n;
    for (int i = 1; i <= n; ++i) {
   
        cin >> v[i] >> w[i] >> s[i];
        if (s[i] == 0) s[i] = m / v[i];
    }

    int q[M];
    for (int i = 1; i <= n; ++i) {
   
        memcpy(g, f, sizeof f);
        for (int r = 0; r < v[i]; ++r) {
   
            int h = 0, t = -1;
            for (int j = r; j <= m; j += v[i]) {
   
                while (h <= t && j - q[h] > s[i] * v[i]) h++;
                while (h <= t && g[j] >= g[q[t]] + (j - q[t]) / v[i] * w[i]) t--;
                q[++t] = j;
                f[j] = g[q[h]] + (j - q[h]) / v[i] * w[i];
            }
        }
    }

    cout << f[m] << "\n";
    return 0;
}