Xếp Lịch (XEPLICH)
Đề bài
Để hưởng ứng ngày quốc tế lao động 1 - 5, năm nay Thành Phố tổ chức buổi lao động tập thể cho tất cả các trường trên địa bàn. Tổng số lớp tham gia là $k$ lớp và số công việc cần giải quyết là $n$ công việc. Do mỗi lớp có số học sinh nam và nữ khác nhau nên hiệu quả khi giải quyết các công việc là khác nhau. Với mỗi lớp $i$, ta biết hiệu quả khi làm công việc $j$ là $v[i,j]$.
Yêu cầu: Hãy sắp xếp công việc cho các lớp thỏa mãn: lớp có số hiệu nhỏ sẽ thực hiện các công việc trước lớp có số hiệu lớn hơn sao cho hiệu quả của buổi lao động thu được là lớn nhất?
Dữ liệu: vào từ tệp văn bản XEPVIEC.INP gồm:
- Dòng đầu tiên là 2 giá trị $k$ và $n$ $(1 \le k \le n \le 100)$.
- Từ dòng thứ 2 trở đi ghi các giá trị $v[i,j]$, với $i = 1..k$ và $j = 1..n$.
Kết quả: ghi ra tệp văn bản XEPVIEC.OUT gồm 1 số duy nhất là hiệu quả lớn nhất thu được.
Giới hạn: thời gian 1 giây, bộ nhớ 512 MB.
(Trên hệ thống chấm online thì đọc dữ liệu từ bàn phím và in ra màn hình như bình thường nhé. Ảnh đề gốc ghi "(<=k<=n<=100)", bị mất số 1 ở đầu, mình ghi lại là $1 \le k \le n \le 100$.)
4 6
1 1 6 4 3 10
9 1 4 7 2 7
7 2 6 10 2 3
6 10 7 1 3 924Lời mở đầu
Bài này đề viết hơi "khó hiểu" một chút nên trước tiên mình sẽ tóm tắt lại đề một cách đơn giản nhất để bạn nào chưa hiểu như sau 😇:
- Mỗi lớp phải thực hiện đúng một công việc (mỗi công việc không quá một lớp).
- Lớp có số thứ tự nhỏ hơn phải làm công việc có số thứ tự nhỏ hơn (công việc trước) lớp có số thứ tự lớn hơn.
Bài này hiện chưa có link nộp, các bạn có thể chạy thử code ở trang Chạy code online của blog với các test ví dụ nhé.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Với $k = 4$, $n = 6$, các ô gạch chân (tô xanh) là các công việc được chọn trong đáp án:
| Việc 1 | Việc 2 | Việc 3 | Việc 4 | Việc 5 | Việc 6 | |
|---|---|---|---|---|---|---|
| Lớp 1 | 1 | 1 | 6 | 4 | 3 | 10 |
| Lớp 2 | 9 | 1 | 4 | 7 | 2 | 7 |
| Lớp 3 | 7 | 2 | 6 | 10 | 2 | 3 |
| Lớp 4 | 6 | 10 | 7 | 1 | 3 | 9 |
Lớp 1, 2, 3, 4 lần lượt làm công việc 1, 3, 4, 6 (chỉ số tăng dần đúng điều kiện) và tổng hiệu quả là $1 + 4 + 10 + 9 = 24$. Các bạn thử tham lam xem: lớp 1 mà chọn việc 6 (hiệu quả 10, lớn nhất hàng) thì các lớp sau hết việc để làm luôn; lớp 2 chọn việc 1 (hiệu quả 9) thì lớp 1 lại không còn việc nào đứng trước. Nên không thể cứ chọn ô lớn nhất được, phải cân nhắc toàn cục – đây chính là chỗ cần đến quy hoạch động.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn bằng đệ quy – hàm mũ
Cách cơ bản nhất chính là vét cạn: xét hết tất cả các trường hợp có thể có, tạo ra mọi độ hiệu quả rồi so sánh, lấy cái lớn nhất thì đó chính là kết quả. Ta dùng đệ quy cho cách này: hàm Try(sttLop, sttCongViec, sum) (stt là số thứ tự) cho lớp sttLop thử lần lượt từng công việc j từ sttCongViec đến $n$, sum là tổng hiệu quả của các lớp trước đó.
- Nếu
sttLoplà lớp $k$ (lớp cuối cùng) thì ta cập nhật kết quảres = max(res, sum + v[sttLop][j]). - Nếu chưa phải lớp cuối thì thử tiếp với lớp
sttLop + 1, bắt đầu từ công việcj + 1(vì lớp sau phải làm công việc nằm sau công việc của lớp trước nó).
Source code cho cách làm vét cạn mình để đây cho anh em cần thì tham khảo nhé:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll k, n, res;
ll v[105][105];
void Try(ll sttLop, ll sttCongViec, ll sum){
for(int j = sttCongViec; j <= n; ++j) {
if(sttLop == k) {
res = max(res, sum + v[sttLop][j]);
}
else {
Try(sttLop + 1, j + 1, sum + v[sttLop][j]);
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 1; i <= k; ++i) {
for(int j = 1; j <= n; ++j) {
cin >> v[i][j];
}
}
Try(1, 1, 0);
cout << res;
return 0;
}import sys
data = sys.stdin.read().split()
k, n = int(data[0]), int(data[1])
v = [[0] * (n + 1) for _ in range(k + 1)]
pos = 2
for i in range(1, k + 1):
for j in range(1, n + 1):
v[i][j] = int(data[pos])
pos += 1
res = 0
def Try(sttLop, sttCongViec, s):
global res
for j in range(sttCongViec, n + 1):
if sttLop == k:
res = max(res, s + v[sttLop][j])
else:
Try(sttLop + 1, j + 1, s + v[sttLop][j])
Try(1, 1, 0)
print(res)2 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất khi code C++ (các bạn cứ gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé). Kinh nghiệm: bài nào cần nhập xuất nhiều thì nên thêm 2 dòng này vào đầu cho chương trình chạy nhanh hơn.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(k \cdot n)$ cho mảng $v$ (cộng thêm độ sâu đệ quy $k$).
- Thời gian: số trường hợp phải xét chính là số cách chọn $k$ công việc có thứ tự tăng dần trong $n$ công việc, tức là $C_n^k$ – một hàm số mũ.
Cách 2Quy hoạch động – O(k·n)
Bài này ta sẽ áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) nhé các bạn. Theo 4 bước giải một bài quy hoạch động:
Bước 1 – Bài toán con: gọi $F[i][j]$ là độ hiệu quả lớn nhất có thể có được khi xét $i$ lớp đầu tiên và $j$ công việc đầu tiên (mỗi lớp trong $i$ lớp đầu làm một việc trong $j$ việc đầu, đúng thứ tự).
Bước 2 – Bài toán cơ sở:
- Ban đầu khởi tạo tất cả $F[i][j] = 0$ để tránh $F[i][j]$ mang giá trị ngẫu nhiên tuỳ compiler (thậm chí giá trị rác) làm sai các bước sau. Cách đơn giản nhất: khai báo mảng $F$ là biến toàn cục thì mọi phần tử được gán mặc định bằng 0.
- Xét 0 lớp nào thì chắc chắn hiệu quả bằng 0: $F[0][j] = 0$.
- Xét 0 công việc nào thì hiệu quả cũng bằng 0: $F[i][0] = 0$.
- Vì lớp số hiệu nhỏ phải làm việc trước, nên lớp thứ $i$ chỉ có thể chọn từ công việc thứ $i$ trở lên (tối thiểu $i - 1$ công việc trước đó dành cho $i - 1$ lớp đầu). Vậy $F[i][j] = 0$ khi $j \lt i$ (trường hợp không hợp lệ, ta để nguyên 0 và không tính).
Bước 3 – Đáp án: quá rõ ràng là $F[k][n]$, vì ta cần hiệu quả lớn nhất khi xét toàn bộ $k$ lớp và $n$ công việc.
Bước 4 – Công thức truy hồi: khi xét $i$ lớp đầu và $j$ công việc đầu ($i \gt 0$, $j \ge i$), ta luôn có 2 lựa chọn:
Minh hoạ điền bảng F và truy vết
Em nhập $k$, $n$ và bảng $v$ (mỗi hàng một lớp, các hàng cách nhau dấu |) rồi bấm Tiếp để xem từng ô $F[i][j]$ được điền. Ô nền xanh nhạt/tím là 2 ô được dùng; cuối cùng mình truy ngược để chỉ ra lớp nào làm việc nào:
Source code cho các bạn tham khảo cách làm trên:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll v[105][105];
ll f[105][105];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int k, n;
cin >> k >> n;
for(int i = 1; i <= k; ++i) {
for(int j = 1; j <= n; ++j) {
cin >> v[i][j];
}
}
for(int i = 1; i <= k; ++i) {
for(int j = 1; j <= n; ++j) {
if(j >= i) f[i][j] = max(f[i][j - 1], f[i - 1][j - 1] + v[i][j]);
}
}
cout << f[k][n];
return 0;
}import sys
data = sys.stdin.read().split()
k, n = int(data[0]), int(data[1])
v = [[0] * (n + 1) for _ in range(k + 1)]
pos = 2
for i in range(1, k + 1):
for j in range(1, n + 1):
v[i][j] = int(data[pos])
pos += 1
f = [[0] * (n + 1) for _ in range(k + 1)]
for i in range(1, k + 1):
for j in range(1, n + 1):
if j >= i:
f[i][j] = max(f[i][j - 1], f[i - 1][j - 1] + v[i][j])
print(f[k][n])Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(k \cdot n)$, thực chất là $O(2 \cdot k \cdot n)$ cho 2 mảng $v$ và $F$.
- Thời gian: $O(k \cdot n)$, thực chất là $O(2 \cdot k \cdot n)$: một lượt đọc bảng $v$ và một lượt điền bảng $F$.
long long cho chắc: tổng của tối đa 100 số, mỗi số cỡ $10^9$ thì đã vượt int rồi.Cách 3Quy hoạch động ngay khi đọc dữ liệu – O(k·n)
Các bạn để ý: khi tính $F[i][j]$ ta chỉ cần đúng một giá trị $v[i][j]$, và các ô được tính theo đúng thứ tự $v$ được đọc vào (hàng trên xuống, trái sang phải). Mà $F[i][j-1]$, $F[i-1][j-1]$ khi đó cũng đã được tính rồi.
x rồi dùng ngay để tính $F[i][j]$. Không cần mảng $v$ nữa, và chỉ còn một lượt duyệt thay vì hai.Đây là source code cho bạn nào muốn tham khảo:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll f[105][105];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int k, n;
cin >> k >> n;
for(int i = 1; i <= k; ++i) {
for(int j = 1; j <= n; ++j) {
ll x;
cin >> x;
if(j >= i) f[i][j] = max(f[i][j - 1], f[i - 1][j - 1] + x);
}
}
cout << f[k][n];
return 0;
}import sys
data = sys.stdin.read().split()
k, n = int(data[0]), int(data[1])
f = [[0] * (n + 1) for _ in range(k + 1)]
pos = 2
for i in range(1, k + 1):
for j in range(1, n + 1):
x = int(data[pos])
pos += 1
if j >= i:
f[i][j] = max(f[i][j - 1], f[i - 1][j - 1] + x)
print(f[k][n])Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(k \cdot n)$, lúc này đúng là $O(k \cdot n)$ rồi (chỉ còn mảng $F$).
- Thời gian: $O(k \cdot n)$, lúc này cũng đúng là $O(k \cdot n)$ (chỉ còn một lượt duyệt).
Ở trường hợp xấu nhất $k = n = 100$ ta chỉ phải làm $100^2 = 10^4$ phép tính, mất khoảng $10^4 / 10^8 = 0.0001$ giây. Nhanh chưa nào anh em, từ cách vét cạn chạy lâu hơn cả tuổi vũ trụ, ta đã rút về còn 0.0001 giây, quá chi là nhanh luôn 😎.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét