烹调方案

一共有n件食材，每件食材有三个属性， a_i ， b_i 和 c_i ，如果在 t 时刻完成第 i 样食材则得到 a_i-t*b_i 的美味指数，用第 i 件食材做饭要花去 c_i 的时间。

在 T 时间内设计烹调方案使得美味指数最大

解题思路：

显然是一个01背包，但是，当你写完01背包板子交上去以后会发现只有30分。

题目中给了一个条件：在 t 时刻完成第 i 样食材则得到 a_i-t*b_i 的美味指数，有了这个条件，显然我们要对每个物品选择的先后性进行讨论了。

设 a_1,b_1,c_1 为第一组物品，a_2,b_2,c_2 为第二组物品， t为当前时间.

将两个物品可获得的值表示出来为：

m_1 = a_1-(t \times c_1) \times b_1 + a_2 - (t+c_1+c_2) \times b_2 m_2 = a_2-(t \times c_2) \times b_2 + a_1 - (t+c_1+c_2) \times b_1

设 m_1 > m_2 得

a_1-(t \times c_1) \times b_1 + a_2 - (t+c_1+c_2) \times b_2 > m_2 = a_2-(t \times c_2) \times b_2 + a_1 - (t+c_1+c_2) \times b_1

拆项得

a_1-b_1t-b_1c_1+a_2-b_2t-b_2c_1-b_2c_2>a_2-b_2t-b_2c_2+a_1-b_1t-b_1c_1-b_1c_2

化简得

b_1c_2 > b_2c_1

由此，我们就得到了我们 sort 函数中cmp的写法。注意开 long long 这题就完了。

这题的关键就在此，我不知道是为什么，大部分题解中都没有给出自己的完整证明，这个证明也不难证，希望读者看完后可以自己证明一遍。

代码：

#include <cstdio>
#include <cctype>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1000100;
const int M = 500010<<1;
inline int read() {
    int x = 0,f = 1;char v = getchar();
    while (!isdigit(v)) {if (v =='-') f = -1;v = getchar();}
    while (isdigit(v)) {x = x * 10 + v - 48;v = getchar();}
    return x * f;
}
int f[N],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[N];
signed main() {
    m = read(),n = read();
    for (int i = 1;i <= n;++i)  pre[i].a = read();
    for (int i = 1;i <= n;++i)  pre[i].b = read();
    for (int i = 1;i <= n;++i)  pre[i].c = read();
    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]);
    }
    printf("%lld",ans);
    return 0;
}