题解 | 压岁钱

同小红升装备

#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int n;
int x;
int y;
int t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> x >> y >> t;
    vector<vector<int>> dp(n + 1, vector<int>(t + 1));
    vector<vector<int>> choice(n + 1, vector<int>(t + 1));
    vector<int> as(n);
    deque<int> dddl;
    for (auto& x : as) {
        cin >> x;
    }
    for (int i = 0; i < n; i++) {
        dp[i + 1] = dp[i];
        int a = as[i];
        int b;
        cin >> b;
        // dp[i] = dp[i - (x + jy)] + jb
        for (int yu = 0; yu < y && x + yu <= t; yu++) {
            dddl.clear();
            for (int j = 0; yu + x + j * y <= t; j++) {
                int l = yu + j * y;
                int r = l + x;
                int val = dp[i][l] - j * b;
                while (dddl.size() && dp[i][yu + y * dddl.back()] - dddl.back() * b < val) {
                    dddl.pop_back();
                }
                dddl.push_back(j);
                if (dddl.front() < j - a) {
                    dddl.pop_front();
                }
                int newDp = dp[i][yu + y * dddl.front()] + (j - dddl.front()) * b;
                // cout << r << ',' << j << ',' << dddl.front() << ',' << newDp << endl;
                if (newDp > dp[i + 1][r]) {
                    dp[i + 1][r] = newDp;
                    choice[i + 1][r] = j - dddl.front();
                }
            }
        }
        // for (int j = 0; j <= t; j++) {
        //     cout << dp[i + 1][j] << ',';
        // }
        // cout << endl;
        // for (int j = 0; j <= t; j++) {
        //     cout << choice[i + 1][j] << ',';
        // }
        // cout << endl;
    }
    // cout << dp[n][t] << endl;
    vector<int> res(n);
    int cc = t;
    for (int i = n - 1; i > -1; i--) {
        int t = choice[i + 1][cc];
        if (t) {
            res[i] = t;
            cc -= x + y * t;
        }
    }
    for (const auto& t : res) {
        cout << t << ' ';
    }
}
// 64 位输出请用 printf("%lld")