Số Zero Tận Cùng
Đề bài
Cho trước một dãy số nguyên dương gồm $n$ phần tử. Nhiệm vụ của bạn rất đơn giản, hãy chọn ra $k$ phần tử từ dãy số đã cho sao cho tích của chúng có nhiều chữ số 0 tận cùng bên phải nhất có thể.
Input
- Dòng thứ nhất gồm 2 số nguyên dương $n, k$ $(k \le n)$.
- Dòng thứ hai gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(a_i \le 10^{18})$ là dãy số cho trước.
Output
- Đưa ra một dòng ghi một số nguyên dương là số chữ số 0 tận cùng bên phải của tích $k$ phần tử được chọn trong cách chọn tối ưu nhất.
Subtask:
- Subtask 1 (60% số điểm): $n \le 20$.
- Subtask 2 (40% số điểm): $n \le 100$.
3 2
50 4 203Lờ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ạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesTrướ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 như sau: cho 2 số nguyên dương $n, k$ với $n \le 100$, $k \le n$; sau đó là $n$ số nguyên dương $a[i]$ với $a[i] \le 10^{18}$. Hãy chọn ra $k$ phần tử từ dãy sao cho tích của $k$ số đã chọn có nhiều chữ số 0 tận cùng bên phải nhất có thể, và in ra số chữ số 0 đó.
Ví dụ: $n = 3$, $k = 2$, $a = \{50, 4, 20\}$. Ta sẽ chọn 2 phần tử là $50$ và $20$, tích của chúng là $50 \times 20 = 1000$, có 3 chữ số 0 ở cuối nên kết quả là $3$.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngSố 0 tận cùng chỉ phụ thuộc mũ 2 và mũ 5
Cách làm đơn giản nhất của bài này chính là vét cạn thôi, tức là ta thử mọi trường hợp: chọn ra mọi tập con có $k$ phần tử, sau đó nhân vào và xem nó có bao nhiêu số 0. Nhưng mà $a[i] \le 10^{18}$ lận, tức là ta phải dùng kiểu long long để lưu; nếu nhân 2 số lớn vậy thì chắc chắn sẽ bị tràn số, vì long long chỉ lưu được tới khoảng $2^{63}$ thôi mà nhân 2 số $10^{18}$ sẽ bằng $10^{36}$. Nếu $k = n = 100$ thì tích tối đa sẽ là $(10^{18})^{100} = 10^{1800}$, không thể lưu trữ nổi nha.
Vậy để xử lý ta cần biết khi nào thì nhân các số vào sẽ có số 0 ở cuối. Với 1 số nguyên $a[i] \ge 2$ thì ta có thể phân tích nó thành thừa số nguyên tố: $a[i] = p_1^{q_1} \cdot p_2^{q_2} \cdots p_k^{q_k}$ với $p$ là các số nguyên tố. Ví dụ: $2 = 2$; $3 = 3$; $6 = 2 \cdot 3$; $20 = 2^2 \cdot 5$; $50 = 2 \cdot 5^2$. Xem vài phép nhân sau:
| Phép nhân | Phân tích | Gộp lại | Kết quả | Số 0 cuối |
|---|---|---|---|---|
| 20 × 50 | (2²·5) · (2·5²) | 2³·5³ | 1000 | 3 |
| 20 × 25 | (2²·5) · (5²) | 2²·5³ | 500 | 2 |
| 20 × 10 | (2²·5) · (2·5) | 2³·5² | 200 | 2 |
| 60 × 40 | (2²·3·5) · (2³·5) | 2⁵·3·5² | 2400 | 2 |
Từ vài ví dụ trên ta sẽ thấy: số 0 ở cuối sẽ chỉ phụ thuộc vào số mũ của 2 và số mũ của 5 mà thôi. Cụ thể kết quả là $2^x \cdot 5^y \cdot (\ldots)$ thì số chữ số 0 ở cuối sẽ bằng $\min(x, y)$, vì mỗi cặp $2 \cdot 5 = 10$ là thêm 1 số 0 ở cuối. $2^3 \cdot 5^3 = 10^3$ có 3 chữ số 0; $2^3 \cdot 5^4$ thì cũng chính là $2^3 \cdot 5^3$ thôi, thừa lại 1 số 5; tương tự với $2^4 \cdot 5^3$, kết quả đều cho ra 3 số 0 ở cuối.
Chính vì vậy khi ta chọn ra được $k$ số thì ta không cần nhân hết chúng vào, mà chỉ cần ở mỗi số phân tích xem nó là $2^{\text{mấy}}$ và $5^{\text{mấy}}$. Vì $2^{x_1} \cdot 2^{x_2} \cdots 2^{x_k}$ $= 2^{x_1 + x_2 + \ldots + x_k}$ nên số mũ của 2 trong tích là $x = x_1 + x_2 + \ldots + x_k$: phần tử đầu phân tích được $2^{x_1}$ thì x += x1, phần tử thứ 2 được $2^{x_2}$ thì x += x2, cứ vậy đến $x_k$. Làm tương tự với 5 ta có $2^x$ và $5^y$, lúc này số số 0 ở cuối là $\min(x, y)$.
Giờ ta sẽ viết một hàm giúp ta biết khi phân tích 1 số $n$ ra thừa số nguyên tố thì số mũ của số nguyên tố $p$ là bao nhiêu, tức $n = \ldots \cdot p^{cnt} \cdot \ldots$ thì hàm trả về $cnt$:
typedef long long ll;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}Đầu tiên ta khởi tạo biến đếm bằng 0, và chừng nào $n$ còn chia hết cho $p$ thì ta tăng biến đếm và lấy $n$ chia cho $p$. Bởi vì $n = \ldots \cdot p^{cnt} \cdot \ldots$ nên $n$ sẽ chia hết cho $p$ được đúng $cnt$ lần. Ví dụ countP(50, 5): $50 \to 10 \to 2$, chia được 2 lần nên trả về 2.
Cách 1Đệ quy chọn / không chọn – O(2^N)
Đầu vào ta lưu mảng a với mỗi phần tử a[i] là một pair<int, int>: .first lưu số mũ của 2, .second lưu số mũ của 5 khi phân tích $a[i]$ ra thừa số nguyên tố. Ta làm vậy để tiện việc khi chọn ra $k$ phần tử thì biết $cnt2$ trong $2^{cnt2}$ và $cnt5$ trong $5^{cnt5}$ của tích $k$ phần tử đó. Cách chọn ra $k$ phần tử như sau:
- Gọi hàm
Try(i, n, k, cnt2, cnt5)trả về số số 0 nhiều nhất ta có thể kiếm được bằng cách chọn $k$ phần tử nằm trong khoảng từ $i$ tới $n$, với lúc đầu ta đã có $2^{cnt2}$ và $5^{cnt5}$. Mảngakhai báo toàn cục. - Điều kiện dừng có 2 phần:
- Khi $k = 0$: không thể chọn thêm phần tử nào nữa, số lượng số 0 kiếm được sẽ là $\min(cnt2, cnt5)$ như đã phân tích ở trên →
return min(cnt2, cnt5); - Khi $i = n + 1$: ta đã đi qua hết tất cả các phần tử mà chắc chắn $k \ne 0$ (vì $k = 0$ thì ở trên đã return rồi), tức là đi hết mà vẫn không chọn đủ $k$ phần tử → trường hợp này không hợp lệ, trả về một giá trị rất bé
INT_MIN$= -2^{31}$. Vì hàm có mục đích tìm lớn nhất nên để trường hợp không hợp lệ không gây ảnh hưởng thì ta phải trả về giá trị bé nhất.
- Khi $k = 0$: không thể chọn thêm phần tử nào nữa, số lượng số 0 kiếm được sẽ là $\min(cnt2, cnt5)$ như đã phân tích ở trên →
- Xử lý chạy: ở mỗi phần tử $i$ ta có 2 lựa chọn là lấy hoặc không lấy. Biến
excl(exclude: không lấy) lưu kết quả của việc không lấy phần tử đó, biếnincl(include: có lấy) lưu kết quả của việc có lấy phần tử đó. Tính xong 2 trường hợp thìreturn max(excl, incl);– trường hợp nào cho nhiều số 0 ở cuối hơn thì lấy trường hợp đó.
Cây lời gọi của Try với ví dụ $a = \{50, 4, 20\}$, $k = 2$ ($50 = 2^1 5^2$, $4 = 2^2$, $20 = 2^2 5^1$): nhánh trái là không lấy, nhánh phải là lấy; ô xanh là $k = 0$ (trả về $\min$), ô đỏ là hết phần tử mà chưa đủ $k$ (trả về INT_MIN), số dưới mỗi ô là giá trị trả về:
Source code về ý tưởng trên cho anh em nào cần tham khảo:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
pii a[105];
int Try(int i, int n, int k, int cnt2, int cnt5) {
if(k == 0) {
return min(cnt2, cnt5);
}
if(i == n + 1) {
return INT_MIN;
}
int excl = Try(i + 1, n, k, cnt2, cnt5);
int incl = Try(i + 1, n, k - 1, cnt2 + a[i].first, cnt5 + a[i].second);
return max(excl, incl);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
ll x;
cin >> x;
a[i] = (pii){countP(x, 2), countP(x, 5)};
}
cout << Try(1, n, k, 0, 0);
return 0;
}import sys
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [None] + [(countP(int(x), 2), countP(int(x), 5)) for x in data[2:2 + n]]
NEG = -(1 << 31) # giống INT_MIN
def Try(i, k, cnt2, cnt5):
if k == 0:
return min(cnt2, cnt5)
if i == n + 1:
return NEG
excl = Try(i + 1, k, cnt2, cnt5)
incl = Try(i + 1, k - 1, cnt2 + a[i][0], cnt5 + a[i][1])
return max(excl, incl)
print(Try(1, k, 0, 0))
sys.setrecursionlimit(10000)
main()Giải thích một số chỗ trong code:
a[i] = (pii){countP(x, 2), countP(x, 5)};ở đây chính là mình ép kiểu dữ liệupair, phải ép thì mới gán được nha.Try(1, n, k, 0, 0): bắt đầu xét từ phần tử 1 tới phần tử $n$, lúc đầu được chọn $k$ phần tử và $cnt2$, $cnt5$ đều bằng 0 vì chưa chọn phần tử nào cả.
Đánh giá độ phức tạp:
Trường hợp xấu nhất mỗi phần tử ta đều có 2 cách chọn là chọn hoặc không, nên $n$ phần tử sẽ có $2^n$ cách chọn. Với $n$ tối đa $= 100$ thì không thể nào thực hiện $2^{100}$ phép tính trong 1 giây được, nên cách trên chắc chắn sẽ bị TLE. Code này ăn được subtask 1 ($n \le 20$), tức 60/100 test. Nếu đi thi mà ta code nhanh ra được cách trên đã là ngon lắm rồi nha.
Cách 2Đệ quy có nhớ (top-down) với mảng 4 chiều
Ở đâu ta đệ quy được thì ở đó ta có thể quy hoạch động top-down được hen: nhờ việc lưu trữ lại kết quả ta sẽ tránh được việc tính đi tính lại các trường hợp đã tính rồi 😇. Từ code trên ta thấy mỗi lần gọi hàm thì chỉ có 4 biến thay đổi: i, k, cnt2 và cnt5. Vậy ta tạo hẳn một mảng 4 chiều để lưu kết quả của hàm Try(); mặc dù có thể tràn bộ nhớ hoặc thậm chí TLE nhưng chúng ta liều ăn nhiều nha, biết đâu lại AC thì sao 🤣.
- $i$ nằm trong khoảng từ 1 tới $n$ nên chiều đầu tiên có kích thước $n$; $k$ thì giảm dần nên to nhất là $k$ →
F[n][k]. - $cnt2$ tối đa là bao nhiêu? Đơn giản là lấy $k$ phần tử có số mũ 2 lớn nhất cộng lại → gọi là
max2. Làm tương tự với 5 →max5. Mảng thànhF[n][k][max2][max5], và phải tạo bằngvector, chứ mảng tĩnh thì không nổi đâu. - Lúc đầu lấp đầy $F = -1$ nghĩa là chưa tính. Sau phần điều kiện dừng ta kiểm tra
!= -1tức là đã từng tính rồi thì return luôn; còn chưa thì tính xong gán vào $F$ rồi mới return.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
pii a[105];
int Try(int i, int n, int k, int cnt2, int cnt5,
vector<vector<vector<vector<int>>>> &f) {
if(k == 0) {
return min(cnt2, cnt5);
}
if(i == n + 1) {
return INT_MIN;
}
if(f[i][k][cnt2][cnt5] != -1) {
return f[i][k][cnt2][cnt5];
}
int excl = Try(i + 1, n, k, cnt2, cnt5, f);
int incl = Try(i + 1, n, k - 1, cnt2 + a[i].first, cnt5 + a[i].second, f);
return f[i][k][cnt2][cnt5] = max(excl, incl);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> calc2, calc5;
for(int i = 1; i <= n; ++i) {
ll x;
cin >> x;
a[i] = (pii){countP(x, 2), countP(x, 5)};
calc2.push_back(countP(x, 2));
calc5.push_back(countP(x, 5));
}
sort(calc2.begin(), calc2.end(), greater<int>());
sort(calc5.begin(), calc5.end(), greater<int>());
int max2 = 0, max5 = 0;
for(int i = 0; i < min(k, (int)calc2.size()); ++i) {
max2 += calc2[i];
}
for(int i = 0; i < min(k, (int)calc5.size()); ++i) {
max5 += calc5[i];
}
vector<vector<vector<vector<int>>>>
f(n + 1, vector<vector<vector<int>>>
(k + 1, vector<vector<int>>
(max2 + 1, vector<int>
(max5 + 1, -1))));
cout << Try(1, n, k, 0, 0, f);
return 0;
}import sys
from functools import lru_cache
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [None] + [(countP(int(x), 2), countP(int(x), 5)) for x in data[2:2 + n]]
NEG = -(1 << 31)
@lru_cache(maxsize=None) # thay cho mảng 4 chiều f[i][k][cnt2][cnt5]
def Try(i, k, cnt2, cnt5):
if k == 0:
return min(cnt2, cnt5)
if i == n + 1:
return NEG
excl = Try(i + 1, k, cnt2, cnt5)
incl = Try(i + 1, k - 1, cnt2 + a[i][0], cnt5 + a[i][1])
return max(excl, incl)
print(Try(1, k, 0, 0))
sys.setrecursionlimit(10000)
main()Với cách trên thì vẫn chỉ được 60/100, mấy test còn lại bị MLE (quá giới hạn bộ nhớ) từ việc tạo vector. Phân tích chút cho các bạn thấy: giả sử trường hợp xấu nhất tất cả các số trong mảng là $10^{18} = 2^{18} \cdot 5^{18}$. Nếu $n = k = 100$ thì $max2 = max5 = 18 \times 100 = 1800$, vector 4 chiều có kích cỡ $100^2 \times 1800^2 = 3.24 \cdot 10^{10}$ ô; chỉ riêng việc gán toàn bộ các phần tử bằng $-1$ thôi đã MLE rồi, nên cách trên vẫn không AC được nha.
Cách 3Quy hoạch động bottom-up 3 chiều
Vậy giờ ta đến với cách quy hoạch động bottom-up, chính là quy hoạch động anh em thường gặp: đi tạo ra công thức truy hồi. Đến cách này mình cải tiến để không dùng mảng 4 chiều nữa. Với ai đã biết cơ bản về quy hoạch động thì ta có 4 bước:
Bước 1: Xác định bài toán con
Ở trên có 4 thứ thay đổi: vị trí phần tử đã xét, số phần tử có thể chọn thêm, số mũ 2 đã lấy được và số mũ 5 đã lấy được. Kết quả số số 0 $= \min(cnt2, cnt5)$, chỉ cần có $cnt2$ và $cnt5$ là có kết quả. Vậy ta cố định số phần tử đã xét, số phần tử đã lấy và số mũ 5 lấy được; còn mũ 2 thì ta ăn nhiều nhất có thể:
Tại sao $[m]$ là số mũ 5 mà không phải số mũ 2? Có lý do cả đấy: giả sử $n = k = 100$, mảng có 100 số $2^{59}$ (vì $\log_2(10^{18}) \approx 59$, số $\le 10^{18}$ có nhiều mũ 2 nhất là $2^{59}$), thì $max2 = 59 \times 100 = 5900$, mảng sẽ có kích thước $100 \times 100 \times 5900$. Còn với 5 thì mỗi phần tử tối đa $5^{25}$ (vì $\log_5(10^{18}) \approx 25$), $max5 = 100 \times 25 = 2500$, ít hơn một nửa; mảng có kích thước $100 \times 100 \times 2500 = 2.5 \cdot 10^7$, hoàn toàn có thể khai báo toàn cục. Để $[m]$ là số mũ 5 giúp dùng ít bộ nhớ hơn và chạy nhanh hơn. Nên các bạn nhớ luôn $max5 = \lfloor \log_5(10^{18}) \rfloor \times 100$ $= 2500$ nha.
Bước 2: Bài toán cơ sở
Lúc đầu fill (lấp đầy) mảng $= -1$, tức là trường hợp đó không tồn tại. Vì nhỡ đâu $max5$ có thể là 10 nhưng không thể tạo ra trường hợp nào có số mũ 5 bằng 6 thì sao; trường hợp đó gọi là không tồn tại, gán $-1$.
Nếu không chọn phần tử nào ($j = 0$) thì xét bao nhiêu phần tử đi nữa ($i$ từ 0 tới $n$), số mũ 5 lấy được luôn bằng 0 ($m = 0$) và số mũ 2 tối đa cũng bằng 0 → $F[i][0][0] = 0$ với $i$ từ 0 tới $n$. Những trường hợp vô nghĩa như xét $i$ phần tử mà chọn $j > i$ (xét 3 phần tử mà chọn tận 4), hay số mũ 5 không thể đạt được, đều là $-1$, đã fill từ đầu nên không phải lo nữa.
Bước 3: Đáp án của bài toán
Đáp án là số số 0 tối đa khi xét $n$ phần tử và chọn $k$ phần tử, nên phải nằm ở $F[n][k]$. $F[n][k][m]$ là số mũ 2 tối đa khi tích có số mũ 5 đúng bằng $m$, nên số số 0 tạo ra là $\min(m, F[n][k][m])$. Cho $m$ chạy từ 0 tới $max5$:
Bước 4: Công thức truy hồi
- Không lấy phần tử thứ $i$: $F[i][j][m]$ $= F[i-1][j][m]$.
- Có lấy phần tử thứ $i$ (gọi số mũ 2, mũ 5 của nó là $cnt2$, $cnt5$). Chỉ lấy được khi: (1) $m \ge cnt5$ – số mũ 5 lấy được phải $\ge$ số mũ 5 của phần tử $i$; và (2) trạng thái trước đó tồn tại: $m = cnt5 + x$ với $x = m - cnt5$, khi xét $i - 1$ phần tử và chọn $j - 1$ phần tử (vì vừa chọn phần tử $i$ rồi) có số mũ 5 là $x$ phải tồn tại, tức $F[i-1][j-1][m - cnt5] \ne -1$. Khi đó ta được $F[i-1][j-1][m-cnt5]$ $+ cnt2$.
nếu $m \ge cnt5$ và $F[i-1][j-1][m-cnt5] \ne -1$ thì $F[i][j][m]$ $= \max(F[i][j][m],\ F[i-1][j-1][m-cnt5] + cnt2)$.
Trước khi xem code, em nhập dãy số và $k$ rồi bấm Tiếp để xem bảng $F$ thay đổi khi lần lượt xét từng phần tử (mỗi bảng là một tầng $F[i]$: hàng là $j$, cột là $m$, ô là số mũ 2 tối đa, ô trống là $-1$):
Source code về ý tưởng trên:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
const int max5 = 2500;
ll a[105];
int f[101][101][max5 + 1];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(&f[0][0][0], &f[100][100][max5 + 1], -1);
for(int i = 0; i <= n; ++i) {
f[i][0][0] = 0;
}
for(int i = 1; i <= n; ++i) {
cin >> a[i];
int cnt2 = countP(a[i], 2), cnt5 = countP(a[i], 5);
for(int j = 1; j <= min(i, k); ++j) {
for(int m = 0; m <= max5; ++m) {
f[i][j][m] = f[i - 1][j][m];
if(m >= cnt5 && f[i - 1][j - 1][m - cnt5] != -1) {
f[i][j][m] = max(f[i][j][m], f[i - 1][j - 1][m - cnt5] + cnt2);
}
}
}
}
int res = 0;
for(int m = 0; m <= max5; ++m) res = max(res, min(m, f[n][k][m]));
cout << res;
return 0;
}import sys
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
max5 = sum(countP(x, 5) for x in a) # tổng mũ 5 tối đa thật sự (<= 2500)
# Chỉ giữ 2 tầng f[i - 1] (prev) và f[i] (cur) của mảng 3 chiều f[i][j][m]
prev = [[-1] * (max5 + 1) for _ in range(k + 1)]
prev[0][0] = 0 # f[0][0][0] = 0
for i in range(1, n + 1):
cnt2, cnt5 = countP(a[i - 1], 2), countP(a[i - 1], 5)
cur = [row[:] for row in prev] # f[i][j][m] = f[i - 1][j][m] (cur[0][0] = 0 sẵn)
for j in range(1, min(i, k) + 1):
pj, cj = prev[j - 1], cur[j]
for m in range(cnt5, max5 + 1):
if pj[m - cnt5] != -1 and pj[m - cnt5] + cnt2 > cj[m]:
cj[m] = pj[m - cnt5] + cnt2
prev = cur
res = 0
for m in range(max5 + 1):
res = max(res, min(m, prev[k][m]))
print(res)Giải thích một số chỗ trong code:
fill(&f[0][0][0], &f[100][100][max5 + 1], -1);lấp đầy cả mảng bằng $-1$ (địa chỉ cuối là ngay sau phần tử cuối cùng của mảng).for$i$ từ 1 tới $n$: $i = 0$ không cần xét vì xét 0 phần tử thì chỉ có $f[0][0][0] = 0$, các $f[0][j][m]$ khác đều $-1$ đã fill từ đầu.for$j$ từ 1 tới $\min(i, k)$: chỉ được chọn tối đa $k$ phần tử, và xét $i$ phần tử thì không thể chọn quá $i$ phần tử.for$m$ từ 0 tới $max5$: đi từ không lấy được số mũ 5 nào đến lấy tối đa.
Không gian: mảng $F$ có $100 \times 100 \times 2500 = 2.5 \cdot 10^7$ ô, mảng $a$ không đáng kể. Thời gian: chính là thời gian lấp đầy mảng $F$, $2.5 \cdot 10^7$ phép tính, vẫn nhỏ hơn $10^8$ nên đảm bảo dưới 1 giây. Với cách này ta đã AC bài này rồi. Việc làm mảng bé hơn cũng giúp chương trình tăng tốc độ chạy đáng kể dù độ phức tạp thời gian như nhau, vì khởi tạo gán mảng ít hơn, truy xuất phần tử cũng nhanh hơn.
Cách 4Bỏ chiều i – mảng 2 chiều, chạy ngược
Giờ đến 1 hướng tiếp cận khác: bỏ đi việc xét bao nhiêu phần tử, mảng $F$ chỉ còn 2 chiều $F[j][m]$ $(0 \le j \le k,\ 0 \le m \le max5)$ = số mũ 2 tối đa lấy được nếu chọn $j$ phần tử và số mũ 5 lấy được là $m$. Để tránh trường hợp một phần tử đang xét bị dùng lặp đi lặp lại thì ta cho cả 2 vòng for chạy ngược. Trước đó for(j) và for(m) là thế này:
for(int j = 1; j <= min(i, k); ++j) {
for(int m = 0; m <= max5; ++m) {
f[i][j][m] = f[i - 1][j][m];
if(m >= cnt5 && f[i - 1][j - 1][m - cnt5] != -1) {
f[i][j][m] = max(f[i][j][m], f[i - 1][j - 1][m - cnt5] + cnt2);
}
}
}Thì bây giờ nó sẽ là thế này:
for(int j = min(i, k); j >= 1; --j) {
for(int m = max5; m >= cnt5; --m) {
if(f[j - 1][m - cnt5] != -1) {
f[j][m] = max(f[j][m], f[j - 1][m - cnt5] + cnt2);
}
}
}$j$ chạy ngược từ $\min(i, k)$ về 1; $m$ chạy ngược từ $max5$ về $cnt5$. Vì đã loại bỏ $[i]$ nên không còn công thức $F[i][j][m]$ $= F[i-1][j][m]$ nữa (giá trị cũ cứ nằm yên trong ô đó chính là trường hợp "không lấy"), ta chỉ còn quan tâm công thức dưới. Mà điều kiện vào được công thức dưới là $m \ge cnt5$, nên cho $m$ chạy từ $max5$ ngược về $cnt5$ thì đỡ phải kiểm tra điều kiện đó.
Xét phần tử $cnt5 = 1, cnt2 = 1$. Tính $F[1][1]$ từ $F[0][0]$, rồi lúc tới $m = 2$ lại đọc $F[1][1]$ vừa được cập nhật bởi chính phần tử này → coi như lấy nó 2 lần.
Ô $F[j-1][m-cnt5]$ nằm ở hàng nhỏ hơn và cột nhỏ hơn, chạy ngược thì nó chưa bị cập nhật ở lượt phần tử $i$ → vẫn là giá trị của $i-1$ phần tử đầu.
Công thức truy hồi: $F[j][m]$ $= \max(F[j][m],\ F[j-1][m-cnt5] + cnt2)$ khi $F[j-1][m-cnt5] \ne -1$. Vòng for $i$ bên ngoài chạy từ đầu mảng đến cuối mảng đã ngầm định là ta đã xét bao nhiêu phần tử rồi. Trường hợp cơ sở cũng chỉ còn $F[0][0] = 0$ (vẫn fill cả mảng bằng $-1$ trước). Đáp án: $res = \max(res, \min(m, F[k][m]))$ với $m$ chạy từ 0 tới $max5$.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
const int max5 = 2500;
ll a[105];
int f[101][max5 + 1];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(&f[0][0], &f[100][max5 + 1], -1);
f[0][0] = 0;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
int cnt2 = countP(a[i], 2), cnt5 = countP(a[i], 5);
for(int j = min(i, k); j >= 1; --j) {
for(int m = max5; m >= cnt5; --m) {
if(f[j - 1][m - cnt5] != -1) {
f[j][m] = max(f[j][m], f[j - 1][m - cnt5] + cnt2);
}
}
}
}
int res = 0;
for(int m = 0; m <= max5; ++m) res = max(res, min(m, f[k][m]));
cout << res;
return 0;
}import sys
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
NEG = -10**9 # thay cho -1 (không tồn tại), cộng thêm vẫn âm
f = [[NEG] * 2501 for _ in range(k + 1)]
f[0][0] = 0
tot5 = 0 # tổng mũ 5 của các phần tử đã xét
for i in range(1, n + 1):
cnt2, cnt5 = countP(a[i - 1], 2), countP(a[i - 1], 5)
tot5 += cnt5
for j in range(min(i, k), 0, -1): # chạy ngược j
src, dst = f[j - 1], f[j]
# m chạy từ cnt5 tới tot5 (lớn hơn tot5 thì chắc chắn không tồn tại)
new = [y + cnt2 for y in src[0:tot5 - cnt5 + 1]]
dst[cnt5:tot5 + 1] = [x if x >= y else y for x, y in zip(dst[cnt5:tot5 + 1], new)]
res = 0
for m in range(tot5 + 1):
res = max(res, min(m, f[k][m]))
print(res)Với cách này thời gian chạy đã nhanh hơn và dùng ít bộ nhớ hơn ($100 \times 2500 = 2.5 \cdot 10^5$ ô). Tuy nhiên không phải bài nào cũng áp dụng được cách trên nha; thường anh em ra đến cách DP bottom-up (Cách 3) mà AC là ok rồi, cách đó dễ hiểu hơn nhiều. Còn Cách 4 thì tuỳ từng bài mới áp dụng được thôi.
| Cách | Ý tưởng | Bộ nhớ (xấu nhất) | Thời gian | Kết quả |
|---|---|---|---|---|
| 1 | Đệ quy chọn / không chọn | $O(n)$ | $O(2^n)$ | 60/100 (TLE) |
| 2 | Đệ quy có nhớ 4 chiều | $3.24 \cdot 10^{10}$ ô | – | 60/100 (MLE) |
| 3 | QHĐ bottom-up $F[i][j][m]$ | $2.5 \cdot 10^{7}$ ô | $O(n \cdot k \cdot max5)$ | AC |
| 4 | QHĐ $F[j][m]$ chạy ngược | $2.5 \cdot 10^{5}$ ô | $O(n \cdot k \cdot max5)$ | AC, nhanh hơn |
Nhận xét
Đăng nhận xét