标签：std node int i64 美味佳肴 inf

美味佳肴

思路：

一个 01 背包，但是要先按照贡献度对 \(m\) 道菜排序，因为贡献值随时间变化而变化，应该在率先更新贡献值最大的菜的前提下来更新接下来的菜
状态转移方程：
\(f(j) = \max(f(j), f(j - c_i) + a_i - b_i * j)\)

关键代码：

#include <bits/stdc++.h>

using i64 = long long;
const i64 inf = 0x3f3f3f3f3f3f;

struct node
{
    i64 a, b, c;
};

bool cmp(node a, node b)
{
    return a.c * b.b < b.c * a.b;
}

int main()
{
    int n, m, t;
    std::cin >> n >> m >> t;
    std::vector<i64>b(n + 1), f(t + 1, -inf);
    std::vector<node>k(m + 1);
    for(int i = 1; i <= n; i++)
    {
        std::cin >> b[i];
    }
    for(int i = 1; i <= m; i++)
    {
        int j;
        std::cin >> j >> k[i].a >> k[i].c;
        k[i].b = b[j];
    }
    std::sort(k.begin() + 1, k.begin() + 1 + m, cmp);
    f[0] = 0;
    for(int i = 1; i <= m; i++)
    {
        for(int j = t; j >= k[i].c; j--)
        {
            f[j] = std::max(f[j], f[j - k[i].c] + k[i].a - k[i].b * j);
        }
    }
    i64 ans = -inf;
    for(int i = 1; i <= t; i++)
    {
        ans = std::max(ans, f[i]);
    }
    std::cout << ans << '\n';
    return 0;
}

标签：std,node,int,i64,美味佳肴,inf
From： https://www.cnblogs.com/zR1K/p/17830121.html