P1417 烹调方案

题面：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$
所以只要满足这个条件的放在前面一定结果更优。
所以，先排序，再背包，做完了。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
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;
}