Nhàm Chán (DPBORE)
Đề bài
DPBORE – Nhàm chán
Sắn không thích sự nhàm chán. Đó là lý do tại sao bất cứ khi nào cậu ta buồn chán, cậu ta nghĩ ra các trò chơi. Một buổi tối mùa đông dài, cậu nghĩ ra một trò chơi và quyết định chơi nó.
Cho một dãy $a$ gồm $n$ số nguyên. Người chơi có thể thực hiện một số bước. Trong một bước duy nhất có thể chọn một phần tử của dãy là $a_k$ và xóa nó, sau đó tất cả các phần tử bằng với $a_k + 1$ và $a_k - 1$ cũng phải bị xóa khỏi dãy. Bước đó mang lại $a_k$ điểm cho người chơi.
Sắn là người cầu toàn, vì vậy anh quyết định lấy càng nhiều điểm càng tốt. Bạn hãy giúp anh ta tính xem trong trường hợp chơi tốt nhất thì anh ta có bao nhiêu điểm.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên $n$ $(1 \le n \le 10^5)$ cho biết có bao nhiêu số trong dãy của Sắn.
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^5)$.
Kết quả: In một số nguyên duy nhất – số điểm tối đa mà Sắn có thể kiếm được.
2
1 223
1 2 349
1 2 1 3 2 2 2 2 310Lời mở đầu
Bài này trên Facebook mình đặt tên là "Trò Chơi", đề gốc trên VinhDinhCoder tên là "Nhàm Chán". Đây là một bài quy hoạch động rất hay vì nó không cho sẵn dãy để ta quy hoạch động ngay, mà ta phải biến đổi đầu vào một chút (đếm, lọc phân biệt, sắp xếp) thì công thức mới lộ ra. Mình sẽ đi từ cách vét cạn bằng đệ quy dễ nghĩ nhất, rồi mới tới cách quy hoạch động để AC nha 😇.
Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu: cho một mảng $a$ có $n$ số nguyên $(1 \le n \le 10^5,\ 1 \le a_i \le 10^5)$. Ở mỗi bước ta chọn một phần tử $a_k$ và xoá nó, sau đó tất cả phần tử có giá trị $a_k + 1$ và $a_k - 1$ cũng bị xoá. Bước đó cho ta $a_k$ điểm. Hãy lấy càng nhiều điểm càng tốt.
Mình giải thích ví dụ 3 để bạn nào chưa hiểu đề sẽ hiểu rõ: $n = 9$, dãy là $1, 2, 1, 3, 2, 2, 2, 2, 3$. Ta thấy có 5 phần tử bằng $2$, 2 phần tử bằng $1$ và 2 phần tử bằng $3$.
- Cách tối ưu là đầu tiên chọn một phần tử $2$: được $2$ điểm, đồng thời mọi phần tử bằng $1$ và bằng $3$ bị xoá sạch. Dãy còn lại 4 phần tử $2$.
- Rồi cứ thế chọn tiếp 4 phần tử $2$ đó (giờ chẳng còn số $1$, số $3$ nào để bị xoá nữa), mỗi lần được $2$ điểm. Tổng cộng $5 \cdot 2 = $ 10.
- Nếu chọn số $1$ và số $3$ thay vì số $2$ thì chỉ được $1 \cdot 2 + 3 \cdot 2 = 8$ điểm, ít hơn.
Tương tự ví dụ 2 với dãy $1, 2, 3$: chọn $2$ thì mất cả $1$ lẫn $3$, chỉ được $2$ điểm; còn chọn $1$ (mất $2$) rồi chọn $3$ thì được $1 + 3 = 4$ điểm, đá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:
Chuẩn bịBiến đổi đầu vào cho dễ làm
Đầu tiên để làm được bài này ta cần thực hiện vài bước nho nhỏ. Ta sẽ dễ dàng nhận thấy là nếu ta chọn một phần tử $2$ thì ta sẽ lấy hết mọi phần tử $2$. Vì khi chọn phần tử $a_i$ thì tất cả phần tử có giá trị $a_i - 1$ và $a_i + 1$ đã bị xoá rồi, nên nếu còn phần tử nào bằng $a_i$ thì ta lấy thêm cũng không ảnh hưởng gì nữa, chỉ có lời. Vậy với ví dụ trên có 5 phần tử $2$ thì khi chọn $2$, điểm nhận được sẽ là $2 \cdot 5 = 10$.
Để làm được điều trên thì ta phải đếm xem mỗi số ở đầu vào xuất hiện bao nhiêu lần. Ta làm việc đó bằng một mảng cnt đếm số lần xuất hiện (đếm phân phối), và một vector a để lưu các phần tử khác nhau. Ví dụ đọc vào được số $3$: ta kiểm tra cnt[3] có bằng $0$ không; nếu có thì đây là lần đầu nó xuất hiện nên cho vào vector a, còn không thì chứng tỏ nó xuất hiện rồi nên không cho vào nữa.
Sau bước trên, vector a chứa các giá trị phân biệt, giờ ta sắp xếp tăng dần. Lúc đó khi xét phần tử $a[i]$ thì ta chắc chắn: phần tử có giá trị $a[i] - 1$ (nếu có) phải nằm ở vị trí $i - 1$, và phần tử có giá trị $a[i] + 1$ (nếu có) phải nằm ở vị trí $i + 1$. Các bạn ngẫm chút là thấy, vì dãy các giá trị phân biệt đã tăng dần mà. Ví dụ ta chọn giá trị $3$ đang ở vị trí số $2$, thì nếu có giá trị $2$ nó phải ở vị trí $1$, nếu có giá trị $4$ nó phải ở vị trí $3$.
push_back(-1) trước một phần tử "giả" ở vị trí $0$ để các giá trị thật được đánh số từ $1$; sau đó gán lại n = a.size() - 1 = số giá trị phân biệt.Với ví dụ 3, sau bước chuẩn bị ta có: $a = [-1,\ 1,\ 2,\ 3]$, $n = 3$, $cnt[1] = 2$, $cnt[2] = 5$, $cnt[3] = 2$.
Cách 1Đệ quy vét cạn – thử mọi cách chọn
Cách làm đầu tiên là vét cạn, tức là ta thử mọi trường hợp. Cách này dùng tới đệ quy nên sẽ hơi phức tạp cho bạn nào chưa quen, nhưng nó là cách dễ nghĩ tới nhất vì ý tưởng chỉ là thử hết các trường hợp có thể xảy ra mà. Mình sẽ phân tích rồi cài đặt để hy vọng các bạn học được thêm điều gì đó.
Ý tưởng: đi lần lượt từ giá trị phân biệt thứ $1$ tới thứ $n$, ở mỗi giá trị ta đứng giữa 2 lựa chọn là không chọn hoặc chọn; khi chọn thì phải kiểm tra xem có được phép chọn hay không. Giả sử ta chọn phần tử $i$, thì khi đi tới phần tử $i + 1$ mà muốn chọn nó, ta phải kiểm tra $a[i + 1] \ne a[i] + 1$ mới được chọn, vì chọn $a[i]$ thì mọi phần tử $a[i] + 1$ đã bị xoá rồi.
Cụ thể ta tạo hàm Try(int i, int notThis, ll sum) giúp thử mọi trường hợp, với:
ilà vị trí phần tử đang xét;notThislà giá trị ta không được lấy (do vừa chọn phần tử trước nó);sumlà tổng điểm đang có.
notThis = 0 (vì $a_i \ge 1$ nên không có giá trị $0$, giá trị tiếp theo kiểu gì cũng khác $0$). Điểm giữ nguyên: Try(i + 1, 0, sum).Try(i + 1, a[i] + 1, sum + a[i] * cnt[a[i]]).Điều kiện dừng: ở trên ta kiểm tra i <= n; vậy khi i > n (trường hợp else) chứng tỏ ta đã có một cách chọn hoàn chỉnh trong $n$ giá trị phân biệt. Ta có biến toàn cục res lưu kết quả và cập nhật res = max(res, sum).
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = (int)1e5;
int cnt[N + 5], n;
ll res = 0;
vector<ll> a;
void Try(int i, int notThis, ll sum) {
if(i <= n) {
Try(i + 1, 0, sum);
if(a[i] != notThis) {
Try(i + 1, a[i] + 1, sum + a[i] * cnt[a[i]]);
}
}
else {
res = max(res, sum);
}
}
int main() {
// freopen("dpbore.inp", "r", stdin);
// freopen("dpbore.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
a.push_back(-1);
for(int i = 1; i <= n; ++i) {
int x;
cin >> x;
if(cnt[x] == 0) {
a.push_back(x);
}
cnt[x]++;
}
sort(a.begin(), a.end());
n = a.size() - 1;
Try(1, 0, 0);
cout << res;
return 0;
}import sys
sys.setrecursionlimit(300000)
N = 10**5
cnt = [0] * (N + 5)
res = 0
a = []
n = 0
def Try(i, notThis, s):
global res
if i <= n:
Try(i + 1, 0, s)
if a[i] != notThis:
Try(i + 1, a[i] + 1, s + a[i] * cnt[a[i]])
else:
res = max(res, s)
data = sys.stdin.read().split()
n = int(data[0])
a.append(-1)
for i in range(1, n + 1):
x = int(data[i])
if cnt[x] == 0:
a.append(x)
cnt[x] += 1
a.sort()
n = len(a) - 1
Try(1, 0, 0)
print(res)Trong code gốc mình có 2 dòng freopen("dpbore.inp", ...) / freopen("dpbore.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 nhé.
Các bạn chạy tay đoạn code trên để thấy cây đệ quy được duyệt như thế nào. Cột bên phải có ngăn xếp lời gọi: dòng trên cùng là lời gọi Try đang chạy, các dòng dưới là những lời gọi đang "chờ" nó trả về:
Giải thích 1 số chỗ trong cách làm ở trên:
a.push_back(-1);vì ta xét các phần tử theo vị trí từ $1$ tới $n$, nên thêm trước 1 phần tử làm phần tử thứ $0$ để các phần tử thêm vào sau bắt đầu từ vị trí $1$. Giá trị $-1$ nhỏ hơn mọi $a_i$ nên sau khi sắp xếp nó vẫn đứng đầu.n = a.size() - 1;vì lúc đầu đã thêm phần tử $-1$ làm phần tử thứ $0$, nên số phần tử khác nhau của dãy chỉ làa.size() - 1.Try(1, 0, 0);bắt đầu từ phần tử đầu tiên nên $i = 1$; lúc đầu chưa có ràng buộc gì nênnotThis = 0; tổng điểmsumlúc đầu cũng bằng $0$.
vector<int> a. Khi đó a[i] * cnt[a[i]] là phép nhân int × int, có thể lên tới $10^5 \cdot 10^5 = 10^{10}$, vượt giới hạn int (khoảng $2.1 \cdot 10^9$) trước khi được cộng vào sum kiểu ll. Ví dụ $n = 10^5$ số đều bằng $10^5$: đáp án đúng là $10^{10}$ nhưng bản vector<int> in ra $1410065408$. Trường hợp này chỉ có 1 giá trị phân biệt nên cách vét cạn chạy tức thì, tức là nó sai thật chứ không phải TLE. Mình đã sửa thành vector<ll> a (giống code cách 2) cho an toàn nha.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$. Ta dùng mảng
cntvà một vector lưu các giá trị khác biệt; trường hợp xấu nhất tất cả phần tử đều khác nhau thì vector có $n$ phần tử như đầu vào. - Thời gian: để tính chính xác thì hơi khó, vì có những nhánh bị chặn (giá trị liền kề). Nhưng nếu các giá trị phân biệt không có cặp nào liền kề nhau thì nhánh nào cũng được đi đủ 2 hướng, số lời gọi lên tới cỡ $2^{n}$ với $n$ là số giá trị phân biệt.
Cách 2Quy hoạch động trên các giá trị phân biệt – O(n log n)
Để AC bài này ta dùng phương pháp Quy Hoạch Động (Dynamic Programming). Cho bạn nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau (nhắc lại: lúc này $n$ là số giá trị phân biệt, $a[1] \lt a[2] \lt \ldots \lt a[n]$ đã sắp xếp):
Bước 1: Xác định bài toán con
Gọi $F[i]$ $(0 \le i \le n)$ là số điểm nhiều nhất ta có thể có được khi xét $i$ phần tử (giá trị phân biệt) đầu tiên.
Bước 2: Xác định bài toán cơ sở
Khi xét $0$ phần tử thì chắc chắn chưa có điểm nào, vậy $F[0] = 0$. Khi xét 1 phần tử đầu tiên thì số điểm lớn nhất chính là $a[1] \cdot cnt[a[1]]$ vì ta chỉ lấy được giá trị đó thôi mà. Chốt lại: $F[0] = 0$; $F[1] = a[1] \cdot cnt[a[1]]$.
Bước 3: Xác định đáp án của bài toán
Hiển nhiên là $F[n]$ rồi; ở đây các bạn lưu ý $n$ là số phần tử khác biệt trong vector mình lưu nha. Ta cần số điểm nhiều nhất khi xét cả $n$ phần tử khác biệt nên đáp án chính là $F[n]$.
Bước 4: Xác định công thức truy hồi
Giả sử ta đang xét phần tử $i$. Ta kiểm tra xem có lấy được nó "thoải mái" không bằng điều kiện a[i] != a[i - 1] + 1.
Trường hợp $a[i] \ne a[i-1] + 1$ (không liền kề với giá trị trước): dù ta có chọn hay không chọn $a[i-1]$ thì $a[i]$ cũng không bị xoá. Lấy nó chỉ có lời, nên $F[i]$ bằng số điểm nhiều nhất khi xét $i - 1$ phần tử đầu tiên cộng với điểm khi lấy $a[i]$:
Trường hợp $a[i] = a[i-1] + 1$ thì sao? Ở đây phải nhớ rằng $F[i]$ lưu số điểm lớn nhất khi xét $i$ phần tử đầu tiên, chứ không bắt buộc phải lấy phần tử thứ $i$ hay không đâu. Tương tự $F[i-1]$ có thể đã lấy hoặc không lấy phần tử $i - 1$, tuỳ trường hợp nào lớn hơn thôi. Bạn nào thấy hơi lú thì đọc chậm lại chút rồi ngẫm là ra nha, lúc này ta đối diện 2 trường hợp:
Vì $F[i]$ là số điểm lớn nhất có thể nên $F[i] = \max(\text{TH1}, \text{TH2})$. Vậy ta có công thức truy hồi:
- Nếu $a[i] = a[i-1] + 1$: $F[i] = \max\big(F[i-1],\ F[i-2] + a[i] \cdot cnt[a[i]]\big)$
- Ngược lại: $F[i] = F[i-1] + a[i] \cdot cnt[a[i]]$
Thử với ví dụ 3: $a = [1, 2, 3]$, điểm mỗi giá trị là $1 \cdot 2 = 2$, $2 \cdot 5 = 10$, $3 \cdot 2 = 6$. $F[0] = 0$, $F[1] = 2$. $a[2] = 2 = a[1] + 1$ nên $F[2] = \max(2,\ 0 + 10) = 10$. $a[3] = 3 = a[2] + 1$ nên $F[3] = \max(10,\ 2 + 6) = 10$ ✅.
Minh hoạ: lấy hay bỏ từng giá trị
Các bạn nhập dãy số rồi bấm Tiếp để xem: đầu tiên dãy được gom thành các giá trị phân biệt kèm số điểm, rồi từng $F[i]$ được tính. Ở bước cuối mình lần ngược lại để chỉ ra những giá trị được chọn:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = (int)1e5;
int cnt[N + 5];
ll f[N + 5];
int main() {
// freopen("dpbore.inp", "r", stdin);
// freopen("dpbore.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<ll> a;
a.push_back(-1);
for(int i = 1; i <= n; ++i) {
int x;
cin >> x;
if(cnt[x] == 0) {
a.push_back(x);
}
cnt[x]++;
}
n = a.size() - 1;
sort(a.begin(), a.end());
f[0] = 0;
f[1] = a[1] * cnt[a[1]];
for(int i = 2; i <= n; ++i) {
if(a[i] == a[i - 1] + 1) {
f[i] = max(f[i - 1], f[i - 2] + a[i] * cnt[a[i]]);
}
else {
f[i] = f[i - 1] + a[i] * cnt[a[i]];
}
}
cout << f[n];
return 0;
}import sys
N = 10**5
cnt = [0] * (N + 5)
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [-1]
for i in range(1, n + 1):
x = int(data[i])
if cnt[x] == 0:
a.append(x)
cnt[x] += 1
n = len(a) - 1
a.sort()
f = [0] * (n + 1)
f[0] = 0
f[1] = a[1] * cnt[a[1]]
for i in range(2, n + 1):
if a[i] == a[i - 1] + 1:
f[i] = max(f[i - 1], f[i - 2] + a[i] * cnt[a[i]])
else:
f[i] = f[i - 1] + a[i] * cnt[a[i]]
print(f[n])for(int i = 2; i <= n; ++i) không chạy lần nào, đáp án là luôn $F[1]$. Còn mảng f có kích thước $10^5 + 5$ nên gán f[1] luôn hợp lệ. Bấm nút Chỉ 1 giá trị ở khung trên để xem nha.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$. Chính xác thì mình dùng tận 3 mảng (
cnt,a,f) nhưng theo quy tắc Big-O thì vẫn là $O(n)$ nha. - Thời gian: đọc và đếm mất $O(n)$, vòng quy hoạch động mất $O(n)$, lớn nhất là bước gọi hàm
sortmất $O(n \log n)$.
vector<ll> a và ll f[] nên phép nhân a[i] * cnt[a[i]] được tính bằng long long, an toà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