Editorial for Duyên Hải 2020 - Lớp 10 - Bài 3 - Phục vụ


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.