题目

动态规划代码 

#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);elsebreak;}}}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';}elsecout << "-1\n";
}