【题解】烹调计划

一共有 n 件食材，每件食材有三个属性，$a[i]，b[i] 和 c[i]$，如果在 t 时刻完成第 $i$样食材则得到 $ai-t*bi$的美味指数，用第 $i$件食材做饭要花去 $c[i]$的时间。
众所周知，gw 的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大。

一开始，我抱着试试看的心态打了一个全裸的 01 背包（不要想歪）。结果，听取 WA 声一片，30 分。
于是我们静下心来，仔细想想。
发现 01 背包的错误在于 $b[i]$，于是我们开始了漫长的颓倒过程。
如果是 i 先做，可得美味指数为：$a[i]−b[i]∗(t+c[i])+a[j]−b[j]∗(t+c[i]+c[j])$
如果是 j 先做，可得美味指数为：$a[j]−b[j]∗(t+c[j])+a[i]−b[i]∗(t+c[i]+c[j])$
设：i 先做比 j 先做的结果大。
则：$a[i]−b[i]∗(t+c[i])+a[j]−b[j]∗(t+c[i]+c[j])>a[j]−b[j]∗(t+c[j])+a[i]−b[i]∗(t+c[i]+c[j])$
那么，等式两边同时减去 $a[i]+a[j]$, 得：$−b[i]∗(t+c[i])−b[j]∗(t+c[i]+c[j])>−b[j]∗(t+c[j])+−b[i]∗(t+c[i]+c[j])$
展开，得：$-b[i]t-b[i]c[i]-b[j]t-b[j]c[i]-b[j]c[j]>-b[j]t-b[j]c[j]-b[i]t-b[i]c[j]-b[i]c[i] $
化简，得：$−b[j]∗c[i]>−b[i]∗c[j] $
最后，按上式排序之后就是常规操作了。
p.s.：一个小细节要开 long long！

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[1000001],n,m,ans;
struct node {
    int a,b,c;
    friend inline bool operator < (const node &rhs,const node &rs) {
        return rhs.b*rs.c > rhs.c*rs.b; 
    }
}pre[1000001];
signed main() {
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i].a;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i].b;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>pre[i].c;
    }
    sort(pre+1,pre+1+n);
    for (int i=1;i<=n;i++) {
        for (int j=m;j>=pre[i].c;j--) {
            f[j]=max(f[j],f[j-pre[i].c]+(pre[i].a-j*pre[i].b));
        }
    }
    for (int i=1;i<=m;i++) {
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    return 0;
}