$O(N^3)$ 的 dp 很好想,也很好 TLE
优化方法
把最优方案变成一种等价的有规律的方案
先把最优方案每只牛按照 x 的值从小到大排序,把最优方案用的总冰激凌按照每只牛 x 的值从小到大重新分配
每 x 个冰激凌换一个硬币,优先小的 x 换,这样从新分配冰激凌,总共换得的硬币不会变少,总共用的冰激凌不会比最优方案多,且总受欢迎度不变
这样我们就把最优方案等价变换成了一种有规律的,方便求解的方案
等于找到了一个范围,指定最优方案存在其中(本题是最优方案和这个范围有交集),即这里存在全局最大值
求这个范围里的最大值,即是全局最大值
分析
通过上述等价变换后的最优方案
所有牛按照 x 从小到大排序后
其冰激凌全分配在序列的前一段的牛上,硬币分配在后一段的牛上,中间的一头牛可能是冰激凌和硬币混合分配的,也可能是全硬币或冰激凌
这样对排好序的序列
从前往后做冰激凌的背包,从后往前做硬币的背包
最后枚举中间混合分配的牛和该牛分的的冰激凌和硬币数,就能枚举出最大值
总复杂度
两个$O(N^2)$ 的背包,一个 $O(N^2)$ 的枚举
总结
对最优方案等价变换成有规律的形式
缩小最大值存在的范围,缩小在一个方便求解的范围内,枚举其中的最大值。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, a, b;
int dp[N][N][2];
struct Node{
int p, c, x;
bool operator< (const Node& w)const{
return x < w.x;
}
}q[N];
int main()
{
scanf("%d%d%d", &n, &a, &b);
for (int i = 1; i <= n; i ++)
{
int p, c, x;
scanf("%d%d%d", &p, &c, &x);
q[i] = {p, c, x};
}
sort(q + 1, q + n + 1);
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= b; j ++)
{
dp[i][j][0] = dp[i - 1][j][0];
int u = q[i].x * q[i].c;
if (j >= u)
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - u][0] + q[i].p);
}
for (int i = n; i; i --)
for (int j = 0; j <= a; j ++)
{
dp[i][j][1] = dp[i + 1][j][1];
if (j >= q[i].c)
dp[i][j][1] = max(dp[i][j][1], dp[i + 1][j - q[i].c][1] + q[i].p);
}
int ans = 0;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= q[i].c; j ++)
if (b >= j * q[i].x && a >= q[i].c - j)
ans = max(ans, dp[i - 1][b - j * q[i].x][0] + dp[i + 1][a - (q[i].c - j)][1] + q[i].p);
printf("%d\n", ans);
return 0;
}