Phi Tiêu (PHITIEU)
Đề bài
PHITIEU – Phi tiêu
Giới hạn thời gian: 1.0 giây. Giới hạn bộ nhớ: 1023 MB.
Sau những giờ thi HSG căng thẳng, BTC tổ chức cho các thí sinh gặp nhau và tham gia các trò chơi giải trí. Trong nội dung phóng phi tiêu, trước khi vào vị trí người chơi được BTC cho quan sát $N$ ô được đánh số từ $1$ đến $N$, trên mỗi ô ghi một số nguyên dương tương ứng với điểm có được nếu người chơi phóng tiêu trúng. Tại mỗi thời điểm người chơi chỉ có thể phóng $1$ cây tiêu và theo nguyên tắc người chơi không được phóng vào $3$ ô liên tiếp nhau.
Yêu cầu: Hãy viết chương trình giúp người chơi chọn các ô để phóng sao cho tổng điểm thu được là lớn nhất. Giả sử tỷ lệ phóng trúng là $100\%$.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên dương $N$ $(1 \le N \le 10^6)$.
- Các dòng tiếp theo chứa $N$ số nguyên dương $a_i$ là số điểm ghi trên các ô $(0 \lt a_i \le 10^9)$.
Kết quả: Một dòng ghi số điểm lớn nhất tìm được.
4
9 3 5 418Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức, kèm theo đó là toàn bộ phần hướng dẫn của mình để bạn nào chưa giải được thì tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Có $4$ ô với điểm $9, 3, 5, 4$. Không được phóng vào $3$ ô liên tiếp, nên không thể lấy cả $4$ ô, cũng không thể lấy $3$ ô liền nhau như ô $2, 3, 4$. Cách tốt nhất là phóng vào ô $1$, ô $3$ và ô $4$ (bỏ ô $2$ chỉ có $3$ điểm): $9 + 5 + 4 = 18$.
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 1Quy hoạch động 4 bước – O(N)
Với yêu cầu không được chọn 3 ô liền nhau và chọn sao cho tổng điểm lớn nhất, bài này áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nhé. Bạn nào đã biết cơ bản qua về quy hoạch động rồi thì 4 bước giải như sau:
Bước 1: Xác định bài toán con
Gọi $f[i]$ là tổng điểm lớn nhất có thể đạt được khi xét qua $i$ vị trí đầu tiên (ô $1$ đến ô $i$), vẫn đảm bảo không có 3 ô liên tiếp nào cùng bị phóng.
Bước 2: Xác định bài toán cơ sở
- $f[0] = 0$ vì không có vị trí nào thì tổng điểm bằng $0$.
- $f[1] = a[1]$ vì chỉ có 1 vị trí thì tổng điểm nhiều nhất là chọn luôn vị trí 1.
- $f[2] = a[1] + a[2]$ vì chỉ có 2 vị trí thì chọn cả 2 (chưa thể có 3 ô liên tiếp).
- $f[3] = \max(a[1] + a[2],\ a[1] + a[3],\ a[2] + a[3])$ vì có 3 vị trí liên tiếp thì không thể chọn cả 3, phải bỏ đi 1 trong 3 và chọn 2 vị trí còn lại – so sánh chọn ra cái lớn nhất.
Bước 3: Xác định đáp án bài toán
Đáp án là $f[N]$ vì ta cần tổng điểm lớn nhất sau khi xét qua cả $N$ vị trí. (Điểm các ô đều dương nên chọn càng nhiều càng có lợi, $f$ là dãy không giảm.)
Bước 4: Xác định công thức truy hồi
Xét ô thứ $i$, có đúng 3 khả năng:
- Không phóng vào ô $i$: $f[i] = f[i - 1]$.
- Phóng ô $i$, không phóng ô $i - 1$: thì ô $i - 2$ hoàn toàn có thể chọn hoặc không, nên $f[i] = f[i - 2] + a[i]$.
- Phóng cả ô $i$ và ô $i - 1$: thì không được phóng ô $i - 2$ (vì không được chọn 3 ô liên tiếp), nên $f[i] = f[i - 3] + a[i] + a[i - 1]$.
Với ví dụ của đề: $f[0] = 0$, $f[1] = 9$, $f[2] = 9 + 3 = 12$, $f[3] = \max(12, 14, 8) = 14$, $f[4] = \max(f[3],\ f[2] + 4,\ f[1] + 4 + 5) = \max(14, 16, 18) = 18$ ✅.
Minh hoạ tính bảng f và lần ngược
Các bạn nhập dãy điểm rồi bấm Tiếp để xem từng $f[i]$ được chọn từ khả năng nào; đi hết bảng thì khung sẽ lần ngược lại (y như phần Mở rộng) để tô ra các ô được phóng:
Đây là code mình code nhanh ra cho em học viên tham khảo:
#include <bits/stdc++.h>
using namespace std;
long long a[(int)1e6 + 1], f[(int)1e6 + 1];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
f[0] = 0;
f[1] = a[1];
if(n > 1){
f[2] = a[1] + a[2];
}
if(n > 2){
f[3] = max(a[1] + a[2], max(a[1] + a[3], a[2] + a[3]));
}
for(int i = 4; i <= n; ++i){
f[i] = max(f[i - 1], max(f[i - 2] + a[i], f[i - 3] + a[i] + a[i - 1]));
}
cout << f[n];
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[i])
f = [0] * (n + 1)
f[0] = 0
f[1] = a[1]
if n > 1:
f[2] = a[1] + a[2]
if n > 2:
f[3] = max(a[1] + a[2], a[1] + a[3], a[2] + a[3])
for i in range(4, n + 1):
f[i] = max(f[i - 1], f[i - 2] + a[i], f[i - 3] + a[i] + a[i - 1])
print(f[n])a, f ra làm biến toàn cục để tránh bị tràn stack. Tốt nhất các mảng lớn các bạn hãy cho nó là toàn cục nha. (Trong bản gốc gửi em học viên, mình lỡ khai báo thêm một mảng cục bộ long long f[n + 1]; trong main – nó "che" mất mảng f toàn cục và chiếm tới 8 MB trên stack, máy nào stack nhỏ (ví dụ Windows mặc định 1 MB) là chạy lỗi ngay. Ở trên mình đã bỏ dòng đó đi, dùng luôn mảng toàn cục.)long long.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho 2 mảng $a$ và $f$.
- Thời gian: $O(N)$ – mỗi $f[i]$ chỉ so sánh 3 khả năng, nên yên tâm AC.
Mở rộngTruy vết – in ra các ô được chọn
Giờ các bạn xem tiếp nha: đề thi gốc không chỉ yêu cầu xuất ra tổng điểm lớn nhất mà còn yêu cầu chỉ rõ những vị trí nào được chọn để đạt tổng điểm đó. Thông thường các bài chỉ cần in ra kết quả lớn nhất thôi, nhưng có một số bài bắt phải truy vết ngược lại để in ra cách chọn. Chỗ này đơn giản là ta lần ngược lại mảng $f$ thôi.
Mình in thử mảng $f$ từ $f[0]$ đến $f[n]$ với ví dụ của đề (thêm đoạn for(int i = 0; i <= n; ++i) cout << f[i] << " "; rồi chạy lại với test 4 / 9 3 5 4), mảng $f$ sẽ là: 0 9 12 14 18.
Nhìn lại công thức $f[i] = \max(f[i - 1],\ f[i - 2] + a[i],\ f[i - 3] + a[i] + a[i - 1])$. Nếu lần ngược xét $f[i]$ với $i$ từ $n$ về $1$:
- Nếu $f[i] = f[i - 1]$: nghĩa là không chọn vị trí $i$ ⇒ xét tiếp $i - 1$.
- Nếu $f[i] = f[i - 2] + a[i]$: nghĩa là chọn vị trí $i$ và không chọn vị trí $i - 1$ ⇒ xét tiếp $i - 2$.
- Nếu $f[i] = f[i - 3] + a[i] + a[i - 1]$: nghĩa là chọn vị trí $i - 1$ và $i$, không chọn $i - 2$ ⇒ xét tiếp $i - 3$.
Ví dụ xét $f[4] = 18$ rơi vào tình huống nào? Thấy $f[4] = f[1] + a[4] + a[3] = 9 + 4 + 5 = 18$, nên đưa vị trí $3, 4$ vào đáp án, rồi nhảy về $f[1]$. Khi $i \le 3$ thì dựa vào điều kiện cơ sở: $f[1] = a[1]$ nghĩa là chọn vị trí $1$. Vậy tổng cộng 3 vị trí được chọn là $1, 3, 4$.
Đây là code đã chỉnh lại để lần ngược ra cụ thể các vị trí chọn, độ phức tạp vẫn là $O(N)$. Kết quả in ra: dòng đầu là số ô được chọn và tổng điểm lớn nhất, sau đó mỗi dòng là một vị trí được chọn (in từ cuối về đầu):
#include <bits/stdc++.h>
using namespace std;
long long a[(int)1e6 + 1], f[(int)1e6 + 1];
int b[(int)1e6 + 1];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
f[0] = 0;
f[1] = a[1];
if(n > 1){
f[2] = a[1] + a[2];
}
if(n > 2){
f[3] = max(a[1] + a[2], max(a[1] + a[3], a[2] + a[3]));
}
for(int i = 4; i <= n; ++i){
f[i] = max(f[i - 1], max(f[i - 2] + a[i], f[i - 3] + a[i] + a[i - 1]));
}
int nb = 0;
int idx;
for(idx = n; idx >= 4; --idx){
if(f[idx] == f[idx - 2] + a[idx]){
b[nb++] = idx;
idx--;
}
else if(f[idx] == f[idx - 3] + a[idx] + a[idx - 1]){
b[nb++] = idx;
b[nb++] = idx - 1;
idx -= 2;
}
}
if(idx == 3){
if(f[3] == a[1] + a[2]){
b[nb++] = 2;
b[nb++] = 1;
}
else if(f[3] == a[1] + a[3]){
b[nb++] = 3;
b[nb++] = 1;
}
else if(f[3] == a[2] + a[3]){
b[nb++] = 3;
b[nb++] = 2;
}
}
else if(idx == 2){
b[nb++] = 2;
b[nb++] = 1;
}
else if(idx == 1){
b[nb++] = 1;
}
cout << nb << " " << f[n];
for(int i = 0; i < nb; ++i){
cout << '\n' << b[i];
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[i])
f = [0] * (n + 1)
f[0] = 0
f[1] = a[1]
if n > 1:
f[2] = a[1] + a[2]
if n > 2:
f[3] = max(a[1] + a[2], a[1] + a[3], a[2] + a[3])
for i in range(4, n + 1):
f[i] = max(f[i - 1], f[i - 2] + a[i], f[i - 3] + a[i] + a[i - 1])
b = []
idx = n
while idx >= 4:
if f[idx] == f[idx - 2] + a[idx]:
b.append(idx)
idx -= 1
elif f[idx] == f[idx - 3] + a[idx] + a[idx - 1]:
b.append(idx)
b.append(idx - 1)
idx -= 2
idx -= 1
if idx == 3:
if f[3] == a[1] + a[2]:
b += [2, 1]
elif f[3] == a[1] + a[3]:
b += [3, 1]
elif f[3] == a[2] + a[3]:
b += [3, 2]
elif idx == 2:
b += [2, 1]
elif idx == 1:
b.append(1)
out = [str(len(b)) + " " + str(f[n])]
out += [str(x) for x in b]
print('\n'.join(out))Giải thích 1 số chỗ trong code:
- Biến
idxkhai báo ngoài vòngforđể sau khi thoát vòng lặp ta còn biết nó dừng ở đâu ($3$, $2$, $1$ hay $0$) mà xử lý phần cơ sở. - Trong vòng lặp, khi chọn ô
idx(bỏ ôidx - 1) mìnhidx--thêm 1 lần, cộng với--idxcủa vòngforlà nhảy vềidx - 2; khi chọn 2 ô thìidx -= 2cộng--idxlà nhảy vềidx - 3; còn không rơi vào 2 trường hợp đó thì chắc chắn $f[idx] = f[idx - 1]$, chỉ lùi 1 ô. - Khi
idx == 3thì so $f[3]$ với 3 cặp ở bước cơ sở;idx == 2thì chọn cả 2 ô đầu;idx == 1thì chọn ô 1;idx == 0thì không còn gì để chọ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