25分求调（在线等）急！！

P1417 烹调方案

Fengxuyang @ 2024-11-10 11:52:25

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node
{
    long long a, b, c;
} f[55];

bool cmp(node x, node y)
{
    return 1ll * x.b * y.c > 1ll * y.b * y.c;
}

long long n, m, dp[100005];

int main()
{
    cin >> m >> n;
    for (long long i = 1; i <= n; i++)
    {
        cin >> f[i].a;
    }
    for (long long i = 1; i <= n; i++)
    {
        cin >> f[i].b;
    }
    for (long long i = 1; i <= n; i++)
    {
        cin >> f[i].c;
    }
    sort(f + 1, f + n + 1, cmp);
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = m; j >= f[i].c; j--)
        {
            dp[j] = max(dp[j], dp[j - f[i].c] + f[i].a - j * f[i].b);
        }
    }
    long long ans = 0;
    for (long long j = 1; j <= m; j++)
    {
        ans = max(ans, dp[j]);
    }
    cout << ans;
    return 0;
}

by Fengxuyang @ 2024-11-10 11:55:06

算了离线了（没人回）QAQ

by zyq777 @ 2024-11-10 12:24:44

比较函数：比较函数 cmp 的逻辑是按 b * c 降序排列，这可能不符合问题的要求。实际上，这个排序可能并不必要，因为后续背包逻辑并不依赖于这个排序。

动态规划数组：dp[j] 数组的初始值没有被初始化。你应该设置 dp[j] 的初始值为负无穷，确保不会误用未初始化的值。

美味指数计算：更新公式中 dp[j - f[i].c] + f[i].a - j * f[i].b 应该注意美味指数计算的时机。关键的在于我们要计算完成一项食物所需的时间以及当前时间与食物相关的美味指数。

最优解的计算：搜索 dp 数组最大值应该是从 0 到 m，而不是从 1 开始。

by zyq777 @ 2024-11-10 12:26:42

@Fengxuyang

by zyq777 @ 2024-11-10 12:29:54

但我上机能力比较垃圾，写不出代码QwQ

by luojun666 @ 2024-11-12 09:42:10

@Fengxuyang

在你的代码中，主要问题出在排序和动态规划更新的方式上。你希望通过最大化美味指数来优化做饭的顺序，同时考虑时间约束。

分析

美味指数的计算方式：
- 美味指数是由公式 a_i - t \times b_i 计算得到的，其中 t 是食材开始做的时刻（从 0 开始）。因此，若食材花费的时间较长，必须提前做，避免过多的时间消耗导致美味指数下降。
动态规划的状态：
- 你需要考虑在不同的时间限制下选择不同的食材组合。在本题中，时间是有限制的，因此可以通过动态规划来实现求解。
食材的选择顺序：
- 在排序部分，比较 f[i].b 和 f[i].c 的方式可能不完全适合，因为你实际上关心的是每个食材完成时获得的美味指数，而不仅仅是单纯的 b \times c。需要根据美味指数的增减趋势来判断食材的做法顺序。

修改点

排序方法：
- 排序时应考虑食材的美味指数与时间的关系。实际效果是希望优先做那些对美味指数影响较大的食材，通常那些 b_i 较大的食材应提前做，以减小美味指数的下降。
动态规划：
- 动态规划的状态需要根据每个食材的时间花费进行更新，确保最大化美味指数。

修改后的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node {
    long long a, b, c;
} f[55];

// 比较函数：根据b和c的比值来决定排序
bool cmp(node x, node y) {
    return 1ll * x.b * y.c > 1ll * y.b * x.c;
}

long long n, m, dp[100005];

int main() {
    cin >> m >> n;

    // 输入a, b, c
    for (long long i = 1; i <= n; i++) {
        cin >> f[i].a;
    }
    for (long long i = 1; i <= n; i++) {
        cin >> f[i].b;
    }
    for (long long i = 1; i <= n; i++) {
        cin >> f[i].c;
    }

    // 按照优化后的排序规则排序
    sort(f + 1, f + n + 1, cmp);

    // 初始化dp数组，dp[j]表示做饭时间为j时的最大美味指数
    for (long long i = 0; i <= m; i++) {
        dp[i] = -1e18;  // 设置一个极小值，表示不可达
    }
    dp[0] = 0;  // 0时间时美味指数为0

    // 动态规划计算最大美味指数
    for (long long i = 1; i <= n; i++) {
        for (long long j = m; j >= f[i].c; j--) {
            // 更新状态，选择当前食材或不选择当前食材
            dp[j] = max(dp[j], dp[j - f[i].c] + f[i].a - j * f[i].b);
        }
    }

    // 求最大美味指数
    long long ans = -1e18;
    for (long long j = 0; j <= m; j++) {
        ans = max(ans, dp[j]);
    }

    cout << ans << endl;
    return 0;
}

关键修改点

比较函数 cmp：
- 你使用了 1ll * x.b * y.c > 1ll * y.b * x.c 来对食材进行排序。此比较方法确保了在处理食材时优先处理那些对美味指数影响更大的食材。
动态规划的更新：
- 动态规划的状态更新部分 dp[j] = max(dp[j], dp[j - f[i].c] + f[i].a - j * f[i].b) 保证了每次选择食材时都能考虑时间的消耗，并且每个食材的美味指数会根据做饭时间的不同进行调整。
初始化 dp 数组：
- 为了确保动态规划的状态正确性，我们将 dp 数组初始化为一个很小的数（-1e18），表示初始状态下某些时间点不可达。然后再用 dp[0] = 0 进行初始化，表示在时间为 0 时，美味指数为 0。
最终结果：
- 最后，通过遍历 dp 数组来获取最大美味指数。

时间复杂度

排序的时间复杂度为 O(n \log n)。
动态规划的时间复杂度为 O(n \times m)。
因此，整体的时间复杂度为 O(n \log n + n \times m)，适用于本题的约束条件。

样例

输入：

输出：

以上修改后的代码将正确计算并输出最大美味指数。

by luojun666 @ 2024-11-12 09:43:11

@Fengxuyang GPT会出手