帮帮我，感激不尽。赏关注

Question

有 n 个人在排队取餐。每个人都有自己的口味偏好，他们会在手机上自助选择好自己想要的餐品。不同的餐品需要不同的制作时间。

你是这家餐厅的老板，作为生意火爆的网红打卡点，你的餐厅营业时间一天只有m分钟。如果某个顾客能够吃到他点的餐品，他会就给餐厅打分。第i个人如果吃到了餐品，他就会给餐厅打x[i]分。但是由于不能马上吃到餐品，顾客就会产生不满。如果第i个人吃到餐品等待了q分钟，他就会减少打分，分数就会减少q∗y[i]，这里y[i]表示顾客每分钟产生的不满度。并且每个顾客有一个等待爆发周期z[i]，即每隔z[i]分钟会直接降低打分30分。当然，只要顾客吃到了餐品，他至少会给餐厅打原本分数的一半。

作为老板，你当然是可以看到所有顾客的要求的。为了让你的餐厅的总分尽量高，你决定调整出餐的顺序。请你根据给出的顾客要求，来安排出餐顺序获得最高的总分。当然不一定每位顾客都能在营业时间内获得餐品。

【输入格式】
第一行输入两个数n,m，表示共有n个人，营业时间为m分钟

接下来输入n行，每行输入四个数x[i],y[i],z[i]，t[i]。x[i]表示第i个顾客如果吃到餐品会打的最高分数，y[i]表示每分钟产生的不满度，z[i]表示等待爆发周期，每个周期减少30分。t[i]表示制作该餐品所需要花费的时间。

【输出格式】
输出一行一个数，表示获得的最高总分。

【输入样例】
2 100
1000 4 30 50
500 2 50 50
【输出样例】
1020
【数据范围】
对于70%的数据，保证n≤10
对于100%的数据，保证n≤20,m≤1000,1≤x[i]≤10000,0≤y[i]≤100,1≤z[i]≤100,1≤t[i]≤100
每个顾客初始的最高分数保证是10的倍数。

Answer 1

这道题目可以使用状态压缩动态规划来解决。我们可以定义状态f[j]表示状态为j时的最大总分。其中j是一个二进制数，第k位为1表示第k个顾客已经吃到了餐品。

然后我们可以枚举下一个出餐的顾客是谁，然后更新状态。具体地，我们可以枚举所有未吃到餐品的顾客k，然后计算出他吃到餐品时的打分，然后更新状态f[j | (1 << k)]。

最后答案就是所有状态中的最大值。

这种方法的时间复杂度为O(m * 2^n * n)，其中n为顾客数量，m为营业时间。

已收到消息. 这道题目可以使用状态压缩动态规划来解决。我们可以定义状态f[j]表示状态为j时的最大总分。其中j是一个二进制数，第k位为1表示第k个顾客已经吃到了餐品。 然后我们可以枚举下一个出餐的顾客是谁，然后更新状态。具体地，我们可以枚举所有未吃到餐品的顾客k，然后计算出他吃到餐品时的打分，然后更新状态f[j | (1 << k)]。 最后答案就是所有状态中的最大值。 这种方法的时间复杂度为O(m * 2^n * n)，其中n为顾客数量，m为营业时间。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << N;
int n, m;
int x[N], y[N], z[N], t[N];
int f[M];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> x[i] >> y[i] >> z[i] >> t[i];
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    for (int i = 0; i < m; i ++ )
        for (int j = 0; j + 1 < 1 << n; j ++ )
        {
            if (f[j] == -0x3f3f3f3f) continue;
            f[j] = max(f[j], f[j]);
            for (int k = 0; k < n; k ++ )
                if (!(j >> k & 1))
                {
                    int score = x[k] - y[k] * (i + t[k]) - (i + t[k]) / z[k] * 30;
                    score = max(score, x[k] / 2);
                    f[j | 1 << k] = max(f[j | 1 << k], f[j] + score);
                }
        }
    int res = 0;
    for (int i = 0; i < 1 << n; i ++ ) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}