Hướng giải của Kế hoạch nấu ăn

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

🍽️ Tối đa hóa độ ngon trong bữa ăn khi quay về Trái Đất

📄 Bài toán:

Có n nguyên liệu/món ăn, mỗi món có \(3\) thuộc tính:
- a[i]: độ ngon ban đầu
- b[i]: mức độ mất ngon theo thời gian
- c[i]: thời gian nấu món
Tổng thời gian nấu không vượt quá T
Độ ngon thực tế khi hoàn thành tại thời điểm t:

\[ \text{taste}_i = a[i] - b[i] \times t \]

🔍 Yêu cầu:

Chọn thứ tự nấu một số món sao cho tổng độ ngon cao nhất

🚀 Ý tưởng giải thuật:

1. ⚠️ Vì sao cần sắp xếp?

Độ ngon mỗi món phụ thuộc vào thời điểm hoàn thành
Càng nấu muộn, độ ngon càng giảm
⇒ Cần nấu trước các món b[i]/c[i] lớn (tức giảm nhanh theo thời gian)

2. Sắp xếp greedy:

Sắp xếp danh sách món theo tỷ lệ: \[ \frac{b[i]}{c[i]} \text{ (giảm dần)} \]

3. Quy hoạch động (Knapsack theo thời gian):

Trạng thái:

dp[t] = độ ngon cao nhất khi sử dụng t thời gian

Khởi tạo:
```
dp[0] = 0, các dp[t>0] = -1
```

Chuyển trạng:

for each dish (a, b, c) theo thứ tự đã sắp xếp:
  for t = T - c → 0:
      if dp[t] != -1:
          finish = t + c
          ngon = a - b * finish
          dp[finish] = max(dp[finish], dp[t] + ngon)

4. Kết quả:

max(dp[0..T])

📊 Độ phức tạp:

Thời gian: \(O(nT)\)
Bộ nhớ: \(O(T)\)

Thuộc kiểu Balo có tổng khối lượng biến đổi và mục tiêu phụ thuộc vào thứ tự duyệt. Cần kết hợp greedy sắp xếp trước khi dp.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 1e5 + 5;

struct Dish {
    int a; // độ ngon ban đầu
    int b; // tốc độ giảm độ ngon theo thời gian
    int c; // thời gian nấu món ăn
} d[MAX];

ll dp[MAX]; // dp[t] = độ ngon tối đa khi dùng đúng t đơn vị thời gian
int T, n;

// Sắp xếp món ăn theo tỉ lệ b/c giảm dần để nấu món giảm nhanh trước
bool cmp(const Dish& x, const Dish& y) {
    return 1LL * x.c * y.b < 1LL * y.c * x.b;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> T >> n;
    for (int i = 0; i < n; ++i) cin >> d[i].a;
    for (int i = 0; i < n; ++i) cin >> d[i].b;
    for (int i = 0; i < n; ++i) cin >> d[i].c;

    sort(d, d + n, cmp); // Greedy: nấu món giảm nhanh trước

    memset(dp, -1, sizeof dp);
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        int a = d[i].a, b = d[i].b, c = d[i].c;
        for (int t = T - c; t >= 0; --t) {
            if (dp[t] == -1) continue;
            int ft = t + c; // thời điểm món ăn hoàn thành
            ll ngon = 1LL * a - 1LL * b * ft;
            if (ngon < 0) ngon = 0; // không cần, nhưng an toàn
            dp[ft] = max(dp[ft], dp[t] + ngon);
        }
    }

    ll res = 0;
    for (int t = 0; t <= T; ++t)
        res = max(res, dp[t]);

    cout << res << '\n';
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.