Hướng dẫn cho Phục vụ (DHBB CT)
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)
\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)
\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)
\(\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