直接 dp 比较困难，考虑套路的用贪心来优化 dp 过程。
设 表示当前考虑了前 个产品，在买车的时候还有 个产品没还完钱，最多可以有多少钱用来买车。简单调整可得买产品的过程中先买 更小的产品再买 更大的产品一定不会让答案更差，因此把所有产品按照 从大到小排序，按照这个顺序处理所有产品即可。
初始条件显然是 。对于 dp 状态 ，当前需要处理第 个产品，可能的转移如下：
- 没有购买第 个产品，。
- 购买第 个产品，且买车的时候还在还债，（最优策略下所有还在还债的产品的购买时间一定是从买车时间开始向前的一段连续后缀）。
- 购买第 个产品，且买车的时候已经还完债了：。
答案即为 。直接模拟上述 dp 流程时间复杂度为 ，可以轻松通过该题。
int a[N], b[N], k[N];
struct Product {
int a, b, d;
} x[N];
int f[510][510];
inline void sol([[maybe_unused]] int CASEID) {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> x[i].a >> x[i].b >> x[i].d;
sort(x + 1, x + n + 1, [&](auto &l, auto &r) { return l.b > r.b; });
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
// f[i][j]: 考虑了前 i 个产品，最后仍然有 j 个产品没有还完钱，最多可以得到多少钱
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= i; ++j) f[i][j] = f[i - 1][j];
for (int j = 0; j <= i; ++j) f[i][j] = max(f[i][j], f[i - 1][j] + x[i].a - x[i].b * x[i].d);
for (int j = 1; j <= i; ++j) f[i][j] = max(f[i][j], f[i - 1][j - 1] + x[i].a - (j - 1) * x[i].b);
} int mx = 0;
for (int i = 0; i <= n; ++i) mx = max(mx, f[n][i]);
cout << mx << '\n';
}
喜欢的话，留下你的评论吧～