Chia Đồ Chơi (DPTOYS)
Đề bài
DPTOYS – Đồ chơi
Sắn rất yêu thích việc mua sắm những đồ chơi khoa học viễn tưởng hiếm và đắt. Anh ta giữ chúng theo một dãy theo thứ tự ngày mua và để trong một cái tủ. Vì vậy, Mì sẽ không bao giờ lấy được đồ chơi của anh ta. Nhưng vì một lần không may mắn, Sắn đã thua Mì trong một vụ cá cược toán học. Và Mì đã yêu cầu Sắn chia sẻ đồ chơi. Bởi vì Sắn không muốn mất nhiều tiền nên anh ta đã quyết định dựa trên một chiến lược để giảm thiểu sự mất mát xuống thấp nhất. Chiến lược đó như sau:
- Đồ chơi được giữ theo thứ tự từ $1..n$.
- Sắn bắt đầu chọn từ đồ chơi đầu tiên ở trong tủ, sẽ lấy $x$ đồ chơi liên tiếp.
- Mì sau đó sẽ chọn đúng $x$ đồ chơi tiếp theo còn lại (chú ý là Mì sẽ chọn số đồ chơi bằng với Sắn, trừ khi số đồ chơi còn lại nhỏ hơn $x$).
- Việc này sẽ tiếp tục cho đến khi không còn lại đồ chơi nào nữa.
Bạn được cho một dãy của đồ chơi với giá của chúng. Hãy giúp Sắn lấy được đồ chơi với số tiền lớn nhất có thể. Sắn chỉ có thể chọn $1$, $2$ hay $3$ đồ chơi ($x$ có giá trị $1$, $2$ hay $3$).
Dữ liệu vào:
- Dòng đầu tiên là $T$, số lượng testcase $(1 \le T \le 10)$.
- Mỗi testcase chứa $N$ ở dòng đầu tiên $(1 \le N \le 10^5)$. Dòng thứ 2 là $N$ số nguyên là giá tiền của các đồ chơi $(1 \le v_i \le 10^9)$.
Kết quả: In ra 1 số nguyên trên một dòng cho mỗi test case là tổng số tiền lớn nhất của các đồ chơi mà Sắn chọn.
2
4
5 4 3 2
6
10 8 7 11 15 2012
53Lời mở đầu
Bài này là một bài quy hoạch động khá hay, 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 😇. Điều thú vị là với mình, cách vét cạn bài này còn khó hơn cách tối ưu nữa 🤣 – các bạn đọc tiếp sẽ thấy.
Trước tiên mình tóm tắt lại đề bài một cách đơn giản nhất cho bạn nào chưa hiểu: có $t$ test ($1 \le t \le 10$), mỗi test có $n$ món đồ chơi ($1 \le n \le 10^5$) với giá $v[1], v[2], \ldots, v[n]$ ($1 \le v[i] \le 10^9$). Ta (Sắn) phải chọn bắt đầu từ món đầu tiên $v[1]$; mỗi lần ta được chọn $x$ món liên tiếp ($1 \le x \le 3$), sau đó ta phải bỏ (nhường cho Mì) $x$ món tiếp theo; cứ thế cho đến khi hết đồ chơi. Mỗi lượt có thể chọn $x$ khác nhau. Hãy chọn sao cho tổng tiền các món ta lấy được là lớn nhất.
Ví dụ $n = 4$, $v = \{5, 4, 3, 2\}$: ta có thể chọn $v[1], v[2]$ rồi phải bỏ $v[3], v[4]$; cũng có thể chọn $v[1]$, bỏ $v[2]$, rồi chọn $v[3], v[4]$ – hoàn toàn thoả mãn. Nhưng không thể chọn $v[1], v[2]$ rồi chọn $v[4]$ được, vì chọn 2 món thì phải bỏ $v[3], v[4]$. Cách chọn tốt nhất là lấy luôn $v[1], v[2], v[3]$ (Mì chỉ còn đúng 1 món $v[4]$ để lấy), được $5 + 4 + 3 = 12$.
Với test thứ hai $v = \{10, 8, 7, 11, 15, 20\}$: Sắn lấy $10, 8$; Mì lấy $7, 11$; Sắn lấy $15, 20$ ⇒ $10 + 8 + 15 + 20 = 53$.
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 – thử mọi cách chọn
Thì cách làm đơn giản nhất của bài này chính là vét cạn. Xin lỗi mình đùa đấy 😆, với mình thì cách vét cạn bài này còn khó hơn cách tối ưu: thời gian mình nghĩ và cài đặt thành công cách vét cạn là gần cả tiếng đồng hồ, gấp đôi thời gian nghĩ ra cách tối ưu. Nhưng mình vẫn cố gắng phân tích để hi vọng các bạn học thêm được điều gì đó.
Ta sẽ đi thử mọi trường hợp có thể. Ví dụ $n = 4$, $v = \{5, 4, 3, 2\}$, ta thử hết: $\{5, 3\}$, $\{5, 3, 2\}$, $\{5, 4\}$, $\{5, 4, 3\}$. Để làm được vậy ta dùng đệ quy: bắt đầu từ phần tử đầu tiên, dùng 1 vòng lặp chọn từ 1 đến 3 phần tử; chọn bao nhiêu thì bỏ bấy nhiêu phần tử tiếp theo, rồi nhảy tới phần tử tiếp theo ta được chọn, lặp lại các bước trên.
Tổng quát lên, gọi hàm Try(i, sum) giúp ta thử mọi trường hợp khi lượt chọn mới bắt đầu ở phần tử $i$ và tổng tiền đang có là sum:
- Chọn phần tử $i$ ⇒ bỏ phần tử $i + 1$ ⇒ gọi tiếp
Try(i + 2)nếu $i + 2 \le n$, còn nếu $i + 2 \gt n$ thì dừng. - Chọn $i, i + 1$ ⇒ bỏ $i + 2, i + 3$ ⇒ gọi tiếp
Try(i + 4)nếu $i + 4 \le n$, không thì dừng. - Chọn $i, i + 1, i + 2$ ⇒ bỏ $i + 3, i + 4, i + 5$ ⇒ gọi tiếp
Try(i + 6)nếu $i + 6 \le n$, không thì dừng.
Mỗi lần dừng lại thì ta cập nhật biến kết quả bằng cách so sánh nó với sum của trường hợp đó. Nó sẽ khá khó hình dung, các bạn chỉ cần nháp ra, suy ngẫm là sẽ ra thôi – hoặc dùng khung chạy tay bên dưới để xem từng lời gọi đệ quy.
Source code cho cách làm vét cạn này để các bạn tham khảo:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll v[(int)1e5 + 5];
ll n, res;
void Try(int i, ll sum) {
for(int j = 1; j <= 3 && i + j - 1 <= n; ++j) {
sum += v[i + j - 1];
if(i + 2 * j <= n) {
Try(i + 2 * j, sum);
}
else {
res = max(res, sum);
}
}
}
int main() {
// freopen("dptoys.inp", "r", stdin);
// freopen("dptoys.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
cin >> n;
res = 0;
for(int i = 1; i <= n; ++i) {
cin >> v[i];
}
Try(1, 0);
cout << res << endl;
}
return 0;
}import sys
sys.setrecursionlimit(10000)
def Try(i, s):
global res
j = 1
while j <= 3 and i + j - 1 <= n:
s += v[i + j - 1]
if i + 2 * j <= n:
Try(i + 2 * j, s)
else:
res = max(res, s)
j += 1
data = sys.stdin.buffer.read().split()
pos = 0
t = int(data[pos]); pos += 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
v = [0] * (n + 1)
for i in range(1, n + 1):
v[i] = int(data[pos]); pos += 1
res = 0
Try(1, 0)
out.append(str(res))
print('\n'.join(out))Trong code gốc mình có 2 dòng freopen("dptoys.inp", ...) / freopen("dptoys.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 yêu cầu đọc ghi file thì bỏ dấu // đi nhé. (Code gốc của mình khai báo mảng v[(int)1e5], nhưng chỉ số chạy tới $n = 10^5$ nên mình nới thành (int)1e5 + 5 cho an toàn.)
Giải thích 1 số chỗ trong code:
j <= 3 && i + j - 1 <= n: vì $j$ chạy từ $1$ tới $3$ nên $i + j - 1$ chính là $i$, $i + 1$, $i + 2$ – món cuối cùng được lấy. Phải check xem nó có $\le n$ không thì mới chạy vào, nếu không sẽ truy cập ra ngoài mảng.i + 2 * j <= n: chọn 1 món $i$ thì nhảy đến $i + 2 = i + 2 \cdot 1$; chọn 2 món thì nhảy đến $i + 4 = i + 2 \cdot 2$; chọn 3 món thì nhảy đến $i + 6 = i + 2 \cdot 3$. Điều kiện này đảm bảo phần tử được chọn tiếp còn trong mảng để gọiTrytiếp, ngược lại thì dừng và cập nhật kết quả.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$ cho mảng $v$ (và độ sâu đệ quy tối đa khoảng $n / 2$).
- Thời gian: tính chính xác thì hơi khó. Gọi $T(n)$ là số cách chia với $n$ món thì $T(n) \approx T(n-2) + T(n-4) + T(n-6)$ – tăng theo hàm mũ, khoảng $1.36^n$. Mình đo thử: $n = 60$ mất khoảng 0.6 giây, $n = 70$ đã mất gần 15 giây.
Cách 2Quy hoạch động trên dãy đảo ngược – O(t·n)
Giờ ta nói về cách làm tốt hơn, giúp ta AC được bài này: áp dụng phương pháp Quy Hoạch Động (Dynamic Programming). Tuy nhiên trước khi áp dụng, riêng với bài này ta phải xử lý dữ liệu một chút:
1 2 3 4 5 thì sau khi đọc vào phải đảo thành 5 4 3 2 1.Lý do tại sao phải đảo ngược? Theo đề bài, đồ chơi được lấy theo chiều từ trái qua phải của input. Nếu xem đồ chơi như là một chồng đĩa, lấy đĩa là lấy từ trên xuống dưới, thì sau khi đảo ngược, đĩa trên cùng (món được lấy đầu tiên) nằm ở vị trí $n$, món thứ hai ở vị trí $n - 1$… Khi đó "còn lại $i$ đĩa" chính là còn lại $v[1..i]$ và đĩa trên cùng là $v[i]$ – rất tiện để viết công thức.
Bước 2 – bài toán cơ sở. Khi chỉ còn $\le 3$ món thì Sắn lấy hết luôn (chọn $x$ đúng bằng số món còn lại) là tốt nhất, vì giá tiền đều dương. Nên $f[1] = v[1]$, $f[2] = v[1] + v[2]$, $f[3] = v[1] + v[2] + v[3]$.
Bước 4 – công thức truy hồi. Với $i \ge 4$ món:
- Trường hợp 1: Sắn lấy 1 món thì Mì lấy 1 món, tức là 2 đĩa đã được lấy. Số tiền của Sắn khi có $i$ đĩa = số tiền khi có $i - 2$ đĩa + $v[i]$: $f[i] = f[i - 2] + v[i]$.
- Trường hợp 2: Sắn lấy 2 đĩa thì Mì cũng lấy 2 đĩa, 4 đĩa đã được lấy: $f[i] = f[i - 4] + v[i] + v[i - 1]$ (từ vị trí $i$ lùi về trước lấy 2 đĩa).
- Trường hợp 3: Sắn lấy 3 đĩa thì Mì cũng lấy 3 đĩa, 6 đĩa đã được lấy: $f[i] = f[i - 6] + v[i] + v[i - 1] + v[i - 2]$.
Minh hoạ bảng f trên dãy đảo ngược
Các bạn nhập dãy giá đồ chơi (theo thứ tự đề cho) rồi bấm Tiếp để xem dãy được đảo ngược, từng $f[i]$ được tính từ 3 lựa chọn nào, và cuối cùng truy ngược ra cách chia tốt nhất:
Source code làm theo cách trên cho các bạn tham khảo:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll v[(int)1e5 + 5];
ll f[(int)1e5 + 5];
int main() {
// freopen("dptoys.inp", "r", stdin);
// freopen("dptoys.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> v[i];
}
int l = 1, r = n;
while(l < r){
swap(v[l], v[r]);
l++;
r--;
}
f[0] = 0;
f[1] = v[1];
f[2] = v[1] + v[2];
f[3] = v[1] + v[2] + v[3];
for(int i = 4; i <= n; ++i){
f[i] = max(f[i - 2] + v[i], max(f[i - 4] + v[i] + v[i - 1], f[max(i - 6, 0)] + v[i] + v[i - 1] + v[i - 2]));
}
cout << f[n] << endl;
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
pos = 0
t = int(data[pos]); pos += 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
v = [0] * (n + 4)
for i in range(1, n + 1):
v[i] = int(data[pos]); pos += 1
l, r = 1, n
while l < r:
v[l], v[r] = v[r], v[l]
l += 1
r -= 1
f = [0] * (n + 4)
f[0] = 0
f[1] = v[1]
f[2] = v[1] + v[2]
f[3] = v[1] + v[2] + v[3]
for i in range(4, n + 1):
f[i] = max(f[i - 2] + v[i], f[i - 4] + v[i] + v[i - 1], f[max(i - 6, 0)] + v[i] + v[i - 1] + v[i - 2])
out.append(str(f[n]))
print('\n'.join(out))Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$, chính xác là $O(2n)$ cho 2 mảng $v$ và $f$.
- Thời gian: $O(t \cdot n)$, chính xác là $O(3 \cdot t \cdot n)$ vì ta phải đọc đầu vào, đảo ngược rồi tính mảng $f$.
int, nên $v$ và $f$ đều là long long nha.Cách 3Quy hoạch động 4 trạng thái – O(t·n)
Đến đây là xong rồi, nhưng bạn nào muốn hack não thêm thì mình trình bày thêm 1 cách nữa cũng dùng quy hoạch động. Nói thật với các bạn, đây là cách ban đầu mình nhìn ra và cài thành công trước; sau đó thấy rắc rối quá mình mới nghĩ lại và đưa ra cách 2 ở trên cho đơn giản hơn. Nhưng đằng nào cũng đã nghĩ và làm ra thì mình cứ viết phân tích ra, xem như một hướng suy nghĩ khác để bạn nào cần có thể tham khảo. Cách này không cần đảo ngược dãy.
Bước 1: Xác định bài toán con
Gọi $F[i][j]$ ($0 \le i \le 3$; $1 \le j \le n$) là số tiền lớn nhất ta có thể có khi đang xét món đồ chơi thứ $j$ và kết thúc ở trạng thái $i$. Quy ước 4 trạng thái:
- $i = 0$: ta không lấy món thứ $j$, và món $j$ là món cuối cùng ta không được lấy trước khi sang lần chọn tiếp theo. Nói cách khác, lần chọn tiếp theo bắt đầu ở vị trí $j + 1$.
- $i = 1$: ta lấy món thứ $j$, và đó là món thứ nhất ta lấy trong lần chọn này.
- $i = 2$: ta lấy món thứ $j$, và đó là món thứ 2 ta lấy trong lần chọn này.
- $i = 3$: ta lấy món thứ $j$, và đó là món thứ 3 ta lấy trong lần chọn này.
Giải thích thêm về $i = 0$: ta lấy 1, 2 hay 3 món liên tiếp thì cũng phải bỏ 1, 2 hay 3 món liên tiếp sau đó. Nếu trước đó ta lấy 3 món thì $j$ ở trạng thái 0 chính là món thứ 3 – món cuối cùng – không được lấy; nếu trước đó lấy 2 món thì $j$ là món thứ 2 không được lấy; lấy 1 món thì $j$ là món duy nhất không được lấy.
Bước 2: Xác định bài toán cơ sở
Có những trạng thái không tồn tại: ở món đầu tiên ta bắt buộc phải chọn, không thể không chọn, cũng không thể là món thứ 2 hay thứ 3 trong lần chọn. Nên $F[0][1]$, $F[2][1]$, $F[3][1]$ không tồn tại, ta gán bằng $-1$. Còn $F[1][1] = v[1]$.
Bước 3: Xác định đáp án bài toán
Đáp án là phần tử lớn nhất trong cả mảng $F$. Sẽ có bạn lầm tưởng đáp án là max của $F[0][n], F[1][n], F[2][n], F[3][n]$ nhưng như thế là sai, vì có trường hợp ta không lấy phần tử cuối mà phần tử cuối cũng không phải là "món cuối cùng ta không được lấy" (ví dụ Sắn lấy 3 món, Mì chỉ còn 1–2 món để lấy).
Bước 4: Xác định công thức truy hồi
1/ $F[0][j]$ – không lấy món $j$, và $j$ là món cuối cùng không được chọn. Có 3 trường hợp:
- Trước đó ta chọn đúng 1 món ở vị trí $j - 1$ ⇒ phải bỏ 1 món là $j$: giá trị $F[1][j - 1]$.
- Trước đó ta chọn 2 món $j - 3, j - 2$ ⇒ bỏ $j - 1$ và $j$: giá trị $F[2][j - 2]$.
- Trước đó ta chọn 3 món $j - 5, j - 4, j - 3$ ⇒ bỏ $j - 2, j - 1, j$: giá trị $F[3][j - 3]$.
⇒ $F[0][j] = \max(F[1][j - 1], F[2][j - 2], F[3][j - 3])$.
2/ $F[1][j]$ – lấy món $j$ và nó là món thứ nhất trong lượt này, nên ngay trước đó phải là món cuối cùng không được chọn ở $j - 1$: $F[1][j] = F[0][j - 1] + v[j]$.
3/ $F[2][j]$ – món $j$ là món thứ 2 ta lấy, nên $j - 1$ phải là món thứ nhất: $F[2][j] = F[1][j - 1] + v[j]$.
4/ $F[3][j]$ – tương tự: $F[3][j] = F[2][j - 1] + v[j]$.
5/ Lưu ý cuối cùng: nếu $F[i - 1][j - 1] = -1$ (trạng thái không tồn tại) thì sao? Ví dụ: có thể chọn món thứ 2 của dãy mà đó là món thứ nhất của lượt chọn đầu không? Dĩ nhiên là không, vì món đầu tiên bắt buộc phải chọn, nên $F[1][2] = -1$; tương tự $F[3][2] = -1$. Vậy khi $F[i - 1][j - 1] = -1$ thì ta gán thẳng $F[i][j] = -1$.
$F[0][j] = \max(F[1][j - 1], F[2][j - 2], F[3][j - 3])$
Với $i$ từ $1$ đến $3$: nếu $F[i - 1][j - 1] = -1$ thì $F[i][j] = -1$, ngược lại $F[i][j] = F[i - 1][j - 1] + v[j]$.
Đáp án $= \max$ của mọi $F[i][j]$.
Đây là source code cho bạn nào muốn tham khảo cách làm này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll v[(int)1e5 + 5];
ll f[4][(int)1e5 + 5];
int main() {
// freopen("dptoys.inp", "r", stdin);
// freopen("dptoys.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
f[0][1] = -1;
f[2][1] = -1;
f[3][1] = -1;
while(t--) {
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> v[i];
}
f[1][1] = v[1];
ll res = f[1][1];
for(int j = 2; j <= n; ++j) {
f[0][j] = f[1][j - 1];
if(j - 2 >= 1) {
f[0][j] = max(f[0][j], f[2][j - 2]);
}
if(j - 3 >= 1) {
f[0][j] = max(f[0][j], f[3][j - 3]);
}
res = max(res, f[0][j]);
for(int i = 1; i <= 3; ++i) {
if(f[i - 1][j - 1] == -1) {
f[i][j] = -1;
}
else {
f[i][j] = f[i - 1][j - 1] + v[j];
res = max(res, f[i][j]);
}
}
}
cout << res << endl;
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
pos = 0
t = int(data[pos]); pos += 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
v = [0] * (n + 1)
for i in range(1, n + 1):
v[i] = int(data[pos]); pos += 1
f = [[0] * (n + 1) for _ in range(4)]
f[0][1] = f[2][1] = f[3][1] = -1
f[1][1] = v[1]
res = f[1][1]
for j in range(2, n + 1):
f[0][j] = f[1][j - 1]
if j - 2 >= 1:
f[0][j] = max(f[0][j], f[2][j - 2])
if j - 3 >= 1:
f[0][j] = max(f[0][j], f[3][j - 3])
res = max(res, f[0][j])
for i in range(1, 4):
if f[i - 1][j - 1] == -1:
f[i][j] = -1
else:
f[i][j] = f[i - 1][j - 1] + v[j]
res = max(res, f[i][j])
out.append(str(res))
print('\n'.join(out))Giải thích 1 số chỗ trong code: if(j - 2 >= 1) và if(j - 3 >= 1) – phải check vậy, không thì ở giai đoạn đầu $j - 2$ hay $j - 3$ nhỏ hơn $1$ sẽ truy cập ra ngoài phần bảng hợp lệ, có thể gây sai kết quả nha các bạn.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$, chính xác là $O(5n)$ cho mảng $v$ và bảng $F$ 4 hàng.
- Thời gian: $O(t \cdot n)$, chính xác là $O(5 \cdot t \cdot n)$ vì phải đọc đầu vào và lấp đầy bảng $F$.
- 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