烹调方案 （公式，DP，背包）

烹调方案

题目链接

题目

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

众所周知，gw的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大。

【数据范围】

对于40%的数据1<=n<=10

对于100%的数据1<=n<=50

所有数字均小于100,000

分析

这道题可以看到背包的影子，但是不同的是价值会不断变化。
所以我们可以尝试推一下式子 （由这道题我们可以看出推式子的重要性）
令(x, y) 为相邻的两件物品，分别列出先取x 和 先取y的价值 ：
(f[x] = a[x] - t * b[x] + a[y] - (t + c[x]) * b[y])
(f[y] = a[y] - t * b[y] + a[x] - (t + c[y]) * b[x])
可以发现 (f[x] > f[y]) 时当且仅当 (c[x] * b[y] < c[y] * b[x]) 。
由此我们可以排下序，然后跑一个裸的 01 背包。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node { int a, b, c; } e[55];
int f[100005], Max = -0x3f3f3f3f, n, m;
bool cmp(node u, node v) { return u.c * v.b < u.b * v.c; }
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> m >> n;
    for(int i = 1; i <= n; ++i) cin >> e[i].a;
    for(int i = 1; i <= n; ++i) cin >> e[i].b;
    for(int i = 1; i <= n; ++i) cin >> e[i].c;
    sort(e + 1, e + n + 1, cmp);
    for(int i = 1; i <= n; ++i) {
        for(int j = m; j >= e[i].c; --j) {
            f[j] = max(f[j], f[j - e[i].c] + e[i].a - j*e[i].b);
            Max = max(Max, f[j]); 
        }
    }
    cout << Max;
    return 0;
}

别忘了开 long long （有可能是负数）。