Hướng dẫn giải của Duyên Hải 2020 - Lớp 10 - Bài 3 - Phục vụ

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: SPyofgame

~\color{orange}{\text{Hướng dẫn}}~

  • Xét đến yêu cầu phục vụ thứ ~i~ tới vị trí ~p~, với 3 nhân viên phục vụ đang ở các vị tri ~a, b, c~ có chi phí phục vụ tối thiểu ~f(i, a, b, c)~ thu được là bao nhiêu ?

~\color{goldenrod}{\text{Tiếp cận}}~

  • Quy hoạch động: xét mảng ~f[i][a][b][c]~ ~\big(~ hoặc hàm ~f(i, a, b, c)~ ~\big)~ như sau

Khi có ~a = b~ hoặc ~b = c~ hoặc ~c = a~, để tiện, ta gọi chi phí lúc này là ~f(i, a, b, c) = +\infty~

Nếu xét hết đơn hàng (~i > k~) thì ~f(i, a, b, c) = 0~

Gọi ~x, y~ là các vị trí bất kì trong ~1 \dots n~

Trương hợp dùng nhân viên ~a~, có chi phí là ~V_A = f(i + 1, p, b, c) + cost(a \rightarrow p) \leq f(i + 1, p, x, y) + cost(a \rightarrow p) + cost(b \rightarrow x) + cost(c \rightarrow y)~ [1]

Trương hợp dùng nhân viên ~b~, có chi phí là ~V_B = f(i + 1, a, p, c) + cost(b \rightarrow p) \leq f(i + 1, x, p, y) + cost(a \rightarrow x) + cost(b \rightarrow p) + cost(c \rightarrow y)~ [2]

Trương hợp dùng nhân viên ~c~, có chi phí là ~V_C = f(i + 1, a, b, p) + cost(c \rightarrow p) \leq f(i + 1, x, y, p) + cost(a \rightarrow x) + cost(b \rightarrow y) + cost(c \rightarrow p)~ [3]

Mình cần tìm giá trị tối thiểu nên ~f(i, a, b, c) = min(V_A, V_B, V_C)~

~\color{purple}{\text{Độ phức tạp}}~

  • Quy hoạch động ~f[i][a][b][c]~ hoặc ~f(i, a, b, c)~:

Số trạng thái ~O(f()) = O(i) \times O(a) \times O(b) \times O(c) = O(m) \times O(n^3)~

Chi phí chuyển ~O(4) = O(1)~

  • Nhận xét tối ưu thời gian:

Gọi yêu cầu phục vụ thứ ~i~ là ~serv_i~ thì kể từ lần thứ ~i \geq 2~, một trong 3 người phục vụ sẽ đang ở vị trí ~serv_{i-1}~ là tối ưu nhất (xem lại [1], [2], [3])

Vậy ta có thể giảm chiều ~O(a)~ hoặc ~O(b)~ hoặc ~O(c)~ thành ~O(1)~

  • Nhận xét tối ưu không gian:

~f(i, a, b, c)~ phụ thuộc ~f(i + 1, x, y, z)~ nên ta cũng có thể giảm chiều ~O(i)~ thành ~O(2)~

Ta chỉ cần một mảng/hàm quy hoạch động cho lần trước và một cái cho lần hiện tại

  • Nhận xét tối ưu hằng số

Không mất tính tổng quát có ~f(i, a, b, c) = f(i, a, c, b) = f(i, b, a, c) = f(i, b, c, a) = f(i, c, a, b) = f(i, c, b, a)~

Nên ta có thể sắp xếp trước để giảm đi ~O(3!)~ hoặc ~O(2!)~ lần

~\color{green}{\text{Code tham khảo }}~: Quy hoạch động

~^{^{\color{purple}{\text{Độ phức tạp : }} O(n^2 \times m)\ \color{purple}{\text{thời gian}}\ ||\ O(n^2 + n \times m)\ \color{purple}{\text{bộ nhớ}}}}~

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

const int LIM_N = 202;
const int LIM_M = 1010;
const int INF = 0x3f3f3f3f;

int serv[LIM_M];
int cost[LIM_N][LIM_N];
int f[2][LIM_N][LIM_N];
int main()
{
    int n, m;
    cin >> n;
    cin >> m;    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> cost[i][j];

    memset(f, +INF, sizeof(f));
    f[0][2][3] = f[0][3][2] = 0;
    int serv = 1;
    for (int t = 1; t <= m; ++t)
    {
        bool cur = t & 1;
        bool pre = !cur;

        int c = serv;
        cin >> serv;
        for (int a = 1; a <= n; ++a)
            for (int b = 1; b <= n; ++b)
                f[cur][a][b] = +INF;

        for (int a = 1; a <= n; ++a)
        {
            if (a == c) continue;
            for (int b = 1; b <= n; ++b)
            {
                if (b == c || b == a) continue;
                if (f[pre][a][b] == +INF) continue;
                minimize(f[cur][a][b], f[pre][a][b] + cost[c][serv]);
                minimize(f[cur][b][c], f[pre][a][b] + cost[a][serv]);
                minimize(f[cur][c][a], f[pre][a][b] + cost[b][serv]);
            }
        }
    }

    int res = +INF;
    bool cur = m & 1;
    for (int a = 1; a <= n; ++a)
        for (int b = 1; b <= n; ++b)
            minimize(res, f[cur][a][b]);

    cout << res;
    return 0;
}

~\color{green}{\text{Code tham khảo }}~: Đệ quy có nhớ

~^{^{\color{purple}{\text{Độ phức tạp : }} O(\frac{1}{2} \times n^2 \times m)\ \color{purple}{\text{thời gian}}\ ||\ O(n^2 \times m)\ \color{purple}{\text{bộ nhớ}}}}~

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

const int LIM_N = 202;
const int LIM_K = 1010;
const int INF = 0x3f3f3f3f;

int serv[LIM_K];
int cost[LIM_N][LIM_N];
int f[2][LIM_N][LIM_N];
int main()
{
    int n, m;
    cin >> n;
    cin >> m;    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> cost[i][j];

    memset(f, +INF, sizeof(f));
    f[0][2][3] = f[0][3][2] = 0;
    int serv = 1;
    for (int t = 1; t <= m; ++t)
    {
        bool cur = t & 1;
        bool pre = !cur;

        int c = serv;
        cin >> serv;
        for (int a = 1; a <= n; ++a)
            for (int b = 1; b <= n; ++b)
                f[cur][a][b] = +INF;

        for (int a = 1; a <= n; ++a)
        {
            if (a == c) continue;
            for (int b = 1; b <= n; ++b)
            {
                if (b == c || b == a) continue;
                if (f[pre][a][b] == +INF) continue;
                minimize(f[cur][a][b], f[pre][a][b] + cost[c][serv]);
                minimize(f[cur][b][c], f[pre][a][b] + cost[a][serv]);
                minimize(f[cur][c][a], f[pre][a][b] + cost[b][serv]);
            }
        }
    }

    int res = +INF;
    bool cur = m & 1;
    for (int a = 1; a <= n; ++a)
        for (int b = 1; b <= n; ++b)
            minimize(res, f[cur][a][b]);

    cout << res;
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.