Trò Chơi 2 (DPGAME2)
Đề bài
DPGAME2 – Trò chơi 2
Giới hạn thời gian: 1.0 giây. Giới hạn bộ nhớ: 128 megabyte.
Cho 1 dãy số gồm $N$ phần tử ($N \le 100000$), mỗi phần tử có 1 giá trị nằm trong khoảng $[-10^9, 10^9]$. Ban đầu, bạn sẽ ở vị trí ô số $0$ với tổng điểm là $0$. Mỗi nước đi, người chơi có thể di chuyển sang phải tối thiểu là $1$ bước và tối đa là $K$ bước ($K \le 100$). Khi dừng lại ở 1 ô nào đó thì giá trị của ô đó sẽ được cộng vào tổng điểm. Bạn có thể dừng cuộc chơi bất cứ lúc nào. Hãy tìm cách chơi sao cho tổng điểm nhận được là nhiều nhất.
Dữ liệu nhập:
- Dòng đầu tiên chứa 2 số $N$, $K$.
- Dòng thứ 2 chứa $N$ số của dãy, mỗi số cách nhau 1 dấu cách.
Kết quả: Số điểm lớn nhất có thể đạt được.
5 2
-2 3 -6 -4 54Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bài này có 2 cái "bẫy" nho nhỏ là ô có thể mang giá trị âm và người chơi được dừng bất cứ lúc nào, các bạn đọc kỹ phần bước 3 bên dưới nha.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Có $N = 5$ ô, mỗi bước nhảy được $1$ hoặc $2$ ô ($K = 2$). Người chơi đứng ở ô $0$ (không có điểm), các ô $1..5$ lần lượt có giá trị:
- Từ ô $0$ nhảy $2$ bước lên ô $2$ (né ô $1$ có $-2$): điểm $= 3$.
- Từ ô $2$ thì bắt buộc phải chạm ô $3$ hoặc ô $4$ (vì mỗi bước tối đa $2$ ô). Chọn ô $4$ (giá trị $-4$, đỡ âm hơn $-6$): điểm $= 3 - 4 = -1$.
- Từ ô $4$ nhảy $1$ bước lên ô $5$: điểm $= -1 + 5 = 4$.
Nếu dừng ngay ở ô $2$ thì chỉ được $3$, còn "liều" đi tiếp tới ô $5$ thì được $4$ – nhiều hơn. Vậy đáp án là 4.
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·K)
Bài này áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nhé các bạn. Cho bạn nào đã biết cơ bản qua về quy hoạch động rồi thì 4 bước giải một bài toán quy hoạch động 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ó được khi xét qua $i$ ô số, tức là tính từ ô đầu tiên (ô thứ 1) và xét đến hết ô thứ $i$, với người chơi đang dừng ở ô $i$ (nên đã nhận điểm của ô $i$).
Bước 2: Xác định bài toán cơ sở
$F[0] = 0$, bởi nếu không đi ô nào hết thì tổng điểm lớn nhất vẫn là $0$ (điểm ban đầu của người chơi).
Bước 3: Xác định đáp án bài toán
Cả thảy ta có $N$ ô số, và đề có nói người chơi có thể dừng bất kỳ lúc nào. Không phải lúc nào $F[N]$ cũng có điểm lớn nhất – điều đó chỉ đúng nếu các ô đều là số dương. Ở đây các ô có thể âm: các bạn tưởng tượng $N = 10$ ô, 5 ô đầu toàn số dương, 5 ô cuối toàn số âm. Rõ ràng điểm lớn nhất là khi dừng ở ô $5$ và lấy được tổng 5 ô đầu; nếu đi tiếp 5 ô sau thì điểm bị giảm, đâu còn lớn nhất nữa.
Vậy đáp án là giá trị lớn nhất trong tất cả các $F[i]$ với $i$ từ $0$ đến $N$.
Bước 4: Xác định công thức truy hồi
Muốn đi đến vị trí $i$ thì trước đó người chơi phải đứng ở một trong các vị trí $i - 1$, $i - 2$, $i - 3$, …, $i - K$ (với tối đa $K$ bước, người chơi nhảy $1$ hay $2$ hay … hay $K$ ô để tới $i$). Để tổng điểm tại $i$ lớn nhất thì ta thử từng vị trí đứng trước đó (mà tổng điểm tại đó cũng đã là lớn nhất), nhảy đến $i$ và nhận thêm điểm $A[i]$, rồi lấy cái lớn nhất:
$F[i] = \max\big(F[i-1] + A[i],\ F[i-2] + A[i],\ \ldots,\ F[i-K] + A[i]\big)$
Để bớt thao tác, thay vì cộng $A[i]$ vào từng $F[i-1], F[i-2], \ldots, F[i-K]$ rồi mới so sánh, ta chỉ cần tìm giá trị lớn nhất của $F[i-1], \ldots, F[i-K]$ rồi cộng $A[i]$ một lần duy nhất:
max(0, i - k).Với ví dụ của đề ($K = 2$): $F[0] = 0$; $F[1] = F[0] + (-2) = -2$; $F[2] = \max(F[0], F[1]) + 3 = 3$; $F[3] = \max(F[1], F[2]) - 6 = -3$; $F[4] = \max(F[2], F[3]) - 4 = -1$; $F[5] = \max(F[3], F[4]) + 5 = 4$. Lớn nhất trong $F[0..5]$ là $4$ ✅.
Minh hoạ cửa sổ K ô trước
Các bạn nhập $K$ và dãy số rồi bấm Tiếp để xem với mỗi ô $i$, "cửa sổ" $K$ ô phía trước được quét ra sao và $F[i]$ lấy theo ô nào:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
// freopen("dpgame2.inp", "r", stdin);
// freopen("dpgame2.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
long long f[n + 1];
long long Max1 = f[0] = 0;
for(int i = 1; i <= n; ++i){
long long Max2 = f[max(0, i - k)];
for(int j = max(0, i - k) + 1; j < i; ++j){
Max2 = max(Max2, f[j]);
}
long long x;
cin >> x;
f[i] = Max2 + x;
Max1 = max(Max1, f[i]);
}
cout << Max1;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
f = [0] * (n + 1)
Max1 = f[0] = 0
for i in range(1, n + 1):
Max2 = max(f[max(0, i - k):i])
x = int(data[1 + i])
f[i] = Max2 + x
Max1 = max(Max1, f[i])
print(Max1)Trong code gốc mình có 2 dòng freopen("dpgame2.inp", ...) / freopen("dpgame2.out", ...) để đọc ghi file. Khi nộp trên CLUE OJ (đọc/ghi chuẩn) thì các bạn để chúng ở dạng chú thích như trên là được; nếu thi offline yêu cầu file thì bỏ dấu // đi nhé.
Giải thích 1 số chỗ trong code:
ios::sync_with_stdio(0); cin.tie(0);giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++ (gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé). Bài này $N$ có thể là $10^5$, tức là cả 100,000 số cần nhập, nên cứ thêm 2 dòng này cho chạy nhanh hơn.Max2lưu giá trị lớn nhất của $F[i-1], F[i-2], \ldots, F[i-K]$ – tức là $K$ vị trí trước $i$. CònMax1lưu giá trị lớn nhất của các $F[i]$ với $i$ từ $0$ đến $N$ – chính là đáp án như đã phân tích ở bước 3.- Ta không cần tạo mảng $A$: các giá trị $A[i]$ được dùng lần lượt với $i$ từ $1$ đến $N$, dùng đúng 1 lần rồi thôi (khi $i = 4$ chỉ cần $A[4]$, không cần gọi lại $A[3], A[2], A[1]$). Nên ta đọc luôn $x$ từ input – $x$ chính là $A[i]$ – rồi cộng vào $F[i]$. Vừa đỡ tốn bộ nhớ cho mảng $A$, vừa khỏi tốn một vòng lặp $N$ lần để đọc dữ liệu, coi như kết hợp đọc input và xử lý luôn.
- Điểm mỗi ô trong đoạn $[-10^9, 10^9]$ nên mảng $F$ phải là
long long. Các bạn tưởng tượng Max của $K$ vị trí trước là $10^9$, cộng thêm $x = 10^9$ là đã $2 \cdot 10^9$ – gần chạm giới hạn củaint; chỉ cần cộng thêm một lần $10^9$ nữa là tràn số. Tổng tối đa có thể tới $10^5 \cdot 10^9 = 10^{14}$, nên dùnglong longcho chắc ăn nhé.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho mảng $F$.
- Thời gian: lặp $N$ lần để tính các $F[i]$, mỗi $F[i]$ xét tối đa $K$ vị trí trước đó, nên tổng quát là $O(N \cdot K)$.
Trường hợp xấu nhất $N = 10^5$, $K = 100$ thì số lần lặp là $10^5 \cdot 10^2 = 10^7$ (10 triệu). Với giới hạn 1 giây, số lần lặp được phép khoảng $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$, nên cách làm này còn ít hơn ngưỡng từ 3 đến 10 lần, yên tâm không bị TLE với C++.
max trên đoạn cắt cho nhanh) với $N = 10^5$, $K = 100$ vẫn mất khoảng 3 giây. Nếu nộp Python mà bị TLE thì các bạn xem phần mở rộng bên dưới, đưa về $O(N)$ là qua.Mở rộngLấy max cửa sổ bằng hàng đợi hai đầu – O(N)
Phần này mình viết thêm cho bạn nào muốn đi xa hơn, với giới hạn của đề thì cách 1 bằng C++ đã đủ AC rồi nha. Để ý ở cách 1, mỗi lần tăng $i$ thì "cửa sổ" $[i-K, i-1]$ chỉ trượt sang phải 1 ô: thêm đúng 1 phần tử mới $F[i-1]$ và bỏ đi đúng 1 phần tử cũ $F[i-K-1]$. Vậy mà ta lại quét lại cả $K$ ô để tìm max – khá phí. Bài toán "max trên cửa sổ trượt" có một kỹ thuật kinh điển là dùng hàng đợi hai đầu (deque) đơn điệu:
- Deque lưu chỉ số các ô trong cửa sổ, sao cho giá trị $F$ tương ứng giảm dần từ đầu tới cuối. Khi đó đầu deque luôn là ô có $F$ lớn nhất trong cửa sổ.
- Trước khi tính $F[i]$: bỏ khỏi đầu deque các chỉ số $\lt i - K$ (đã trượt ra ngoài cửa sổ).
- $F[i] = F[\text{đầu deque}] + A[i]$.
- Đưa $i$ vào cuối deque: trước đó bỏ hết các chỉ số ở cuối có $F \le F[i]$ – vì chúng vừa cũ hơn vừa không lớn hơn $F[i]$, sẽ không bao giờ là max nữa.
Mỗi chỉ số vào deque 1 lần và ra tối đa 1 lần, nên tổng cộng chỉ $O(N)$, không còn phụ thuộc $K$.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<long long> f(n + 1);
deque<int> dq;
f[0] = 0;
dq.push_back(0);
long long Max1 = 0;
for(int i = 1; i <= n; ++i){
while(dq.front() < i - k){
dq.pop_front();
}
long long x;
cin >> x;
f[i] = f[dq.front()] + x;
Max1 = max(Max1, f[i]);
while(!dq.empty() && f[dq.back()] <= f[i]){
dq.pop_back();
}
dq.push_back(i);
}
cout << Max1;
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
f = [0] * (n + 1)
dq = deque([0])
Max1 = 0
for i in range(1, n + 1):
while dq[0] < i - k:
dq.popleft()
f[i] = f[dq[0]] + a[i - 1]
if f[i] > Max1:
Max1 = f[i]
while dq and f[dq[-1]] <= f[i]:
dq.pop()
dq.append(i)
print(Max1)
main()- 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