## Thuật toán ngây thơ
Gọi $\texttt{dp}[i][j]$ là tích lớn nhất có thể đạt được khi xét $i$ phần tử đầu tiên, chữ số tận cùng là $j$.
Trường hợp cơ sở là $\texttt{dp}[i][a_i \ \textrm{mod} \ 10] = a_i$, mô hình quy hoạch động này khá cơ bản với công thức chuyển trạng thái như sau:
- Không chọn $a_i$: $\texttt{dp}[i - 1][j] \rightarrow \texttt{dp}[i][j]$
- Chon $a_i$: $\texttt{dp}[i - 1][j] \times a_i \rightarrow \texttt{dp}[i][(j\times a_i) \ \textrm{mod} \ 10]$
Mỗi lần chuyển trạng thái ta luôn cực đại hóa các giá trị $\texttt{dp}$. Kết quả của bài toán là $\texttt{dp}[n][d]$.
Tuy nhiên, tích các số có thể lên đến $1000^{10^5}$ nên ta cần lưu mảng $\texttt{dp}$ bằng bignum dẫn đến chi phí chuyển trạng thái cao.
$\rightarrow$ Đây là điểm ta cần tối ưu.
## Thuật toán chuẩn
Ta nhắc lại tính chất của phép logarit như sau:
$\log(a \times b) = \log(a) + \log(b)$
Như vậy để biểu diễn độ lớn của một tích $x_1 \times x_2 \times \ldots \times x_k$, ta có thể lưu:
$$
\log(x_1) + \log(x_2) + \ldots + \log(x_k)
$$
Qua đó, ta có thể tối ưu cách lưu trữ mảng $\texttt{dp}$ ở trên bằng cách chỉ lưu tổng cách logarit, khi đó giá trị lớn nhất của $\texttt{dp}$ chỉ có thể là $10^5 \times \log(1000)$ (tùy vào cách bạn chọn cơ số cho $\log$).
Để tính tích lớn nhất tránh các sai số khi làm tròn, ta tạo mảng $\texttt{trace}$ để truy vết phương án chọn số sau đó tính tích của chúng, lúc này các phép tính chỉ được thực hiện trên số nguyên.
Độ phức tạp của thuật toán là $\mathcal{O}(10 \times n)$.
```cpp
for (int i = 1; i <= n; ++i) {
ld val = log2(a[i]);
dp[i][a[i] % 10] = val;
for (int j = 0; j <= 9; ++j) {
int nxt = (j * a[i]) % 10;
if (dp[i - 1][j] != 0 && dp[i - 1][j] + val >= dp[i][nxt]) {
dp[i][nxt] = dp[i - 1][j] + val;
trace[i][nxt] = {i - 1, j};
}
if (dp[i - 1][j] > dp[i][j]) {
dp[i][j] = dp[i - 1][j];
trace[i][j] = {i - 1, j};
}
}
}
```
chithanhnguyen
Created at
2 likes