题面：https://www.luogu.org/problemnew/show/P1417
题意
一共有$n$件食材，每件食材有三个属性，$a_i$，$b_i$和$c_i$，如果在$t$时刻完成第$i$样食材则得到$a_i-t \cdot b_i$的美味指数，用第$i$件食材做饭要花去$c_i$的时间。求T时间内能到达的最大美味指数。
解法
看上去很像一道01背包的问题。事实上一开始我也是直接按照01背包写的但只过了30%的数据点。
关键在于这里存在一个$b_i$，这会导致两个相邻的物品先放和后放导致的结果不同。如果不考虑放物品的顺序直接dp的话就有可能会出错。
考虑两个物品$i$和$j$，假设当前时间为$p$
$i$先放：$A=a_i-(p+c_i) \cdot b_i + a_j - (p+c_i+c_j)\cdot b_j$
$j$先放：$B=a_j-(p+c_j) \cdot b_j + a_i - (p+c_i+c_j)\cdot b_i$
$A>B=>c_j \cdot b_i > c_i \cdot b_j$
所以只要满足这个条件的放在前面一定结果更优。
所以，先排序，再背包，做完了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
const int maxn = 1e5 + 10;
struct node{
ll a, b, c;
bool operator < (node p) const{
return c * p.b < p.c * b;
}
};
node p[maxn];
ll dp[maxn];//dp[j]表示时间为j时的最大美味指数
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, T;
cin >> T >> n;
for(int i = 0; i < n; i++)
cin >> p[i].a;
for(int i = 0; i < n; i++)
cin >> p[i].b;
for(int i = 0; i < n; i++)
cin >> p[i].c;
sort(p, p + n);
ll ans = 0;
for(int i = 0; i < n; i++)
{
for(int j = T; j >= p[i].c; j--)
{
dp[j] = max(dp[j], dp[j - p[i].c] + p[i].a - j * p[i].b);
ans = max(dp[j], ans);
}
}
cout << ans << endl;
return 0;
}