单调队列优化

发现 DP 式子除了一个初始价格以外和部分背包类似，于是直接使用相同的方式优化，时间复杂度。

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

using ll = long long;

ll dp[301][301];

int n;
int x;

void Solve() {
    cin >> n >> x;
    int att, price, cost, upgrade, lvmax;
    deque<ll> dddl;
    for (int i = 0; i < n; i++) {
        cin >> att >> price >> cost >> upgrade >> lvmax;
        for (int j = 0; j < price && j <= x; j++) {
            dp[i + 1][j] = dp[i][j];
        }
        for (int yu = 0; yu < cost && yu + price <= x; yu++) {
            dddl.clear();
            for (int j = 0;; j++) {
                int pos = yu + j * cost + price;
                if (pos > x) {
                    break;
                }
                if (dddl.size() && dddl.front() < j - lvmax) {
                    dddl.pop_front();
                }
                ll newVal = dp[i][yu + j * cost] - (ll)upgrade * j;
                while (dddl.size() &&
                        dp[i][yu + dddl.back() * cost] - (ll)upgrade * dddl.back() < newVal) {
                    dddl.pop_back();
                }
                dddl.push_back(j);
                dp[i + 1][pos] = max(dp[i][pos],
                                     dp[i][yu + dddl.front() * cost] + upgrade * (j - dddl.front()) + att);
            }
        }
        // for (int j = 0; j <= x; j++) {
        //     cout << dp[i][j] << ',';
        // }
        // cout << endl;
    }
    cout << dp[n][x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}