【小蓝的旅行计划——带悔贪心（优先队列）、线段树】

题目

动态规划代码 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int f[N][N];
int main()
{
    memset(f, 0x3f, sizeof f);
    int n, m;
    cin >> n >> m;

    f[0][m] = 0;
    for (int i = 1; i <= n; i++)
    {
        int d, w, l;
        cin >> d >> w >> l;
        for (int j = 0; j <= m; j++)
        {
            for (int k = 0; k <= l; k++)
            {
                if(j - d < 0) continue; //未到
                else if (j + k - d <= m) //到了，且买完之后
                    f[i][j + k - d] = min(f[i][j + k - d], f[i - 1][j] + w * k);
                else
                    break;
            }
        }
    }

    cout << f[n][0];
}

带悔贪心（优先队列）代码 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<int, ll>;
#define x first
#define y second
const int N = 2e5 + 10;
int d[N], w[N], l[N];
multiset<pll> ms;
int n, m;
ll lf; // 剩余油量
ll ans; // 总花费
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> d[i] >> w[i] >> l[i];
        
    ms.insert({0, m});
    lf = m;
    bool can = true; // 可行性
    for (int i = 1; i <= n; i++)
    {
        lf -= d[i];
        if (lf < 0)
        {
            can = false;
            break;
        }

        // 用便宜油
        while (d[i] > 0)
        {
            auto u = *ms.begin();
            auto x = u.x;
            auto y = u.y; // x是价格，y是量
            if (d[i] >= y)
            {
                d[i] -= y;
                ms.erase(ms.begin());
            }
            else
            {
                y -= d[i];
                d[i] = 0;
                ms.erase(ms.begin());
                ms.insert({x, y});
            }
        }

        // 全部购买
        lf += l[i];
        ans += (ll)w[i] * l[i];
        ms.insert({w[i], l[i]});

        // 退贵油
        while (lf > m)
        {
            auto u = *prev(ms.end());
            auto x = u.x;
            auto y = u.y;
            if (lf - m >= y)
            {
                ans -= x * y;
                lf -= y;
                ms.erase(prev(ms.end()));
            }
            else
            {
                ans -= (lf - m) * x;
                y -= lf - m;
                lf = m;
                ms.erase(prev(ms.end()));
                ms.insert({x, y});
            }
        }
    }

    if (can)
    {
        for (auto u : ms)
        {
            auto x = u.x;
            auto y = u.y;
            ans -= x * y; 
        }

        cout << ans << '\n';
    }
    else
        cout << "-1\n";
}