# HD Số 0 tận cùng lqdoj/lastzerohsg
> Trần Hữu Nam - 24/1/2023

Trong các cách chọn i số mà tổng các thừa số 5 là j thì ta chọn cách có số thừa số 2 nhiều nhất, gọi số thừa số 2 nhiều nhất đó là F[i][j].

Ban đầu, F[i][j]=0 hết.

Gọi P2[i], P5[i] lần lượt là số thừa số 2 và số thừa số 5 trong A[i].

Với mỗi số A[x], ta xem thử nó có tham gia vào việc chọn i số để có tổng thừa số 5 là j hay không:

F[i][j]=max(F[i][j], F[i-1][j-P5[x]]+P2[x]);

Cách tính F[i][j]:
* Fill mảng F[][]=0 hết;
* Với mỗi x chạy từ 1 đến n:
* Với mỗi i chạy lùi từ k về 1:
* Với mỗi j chạy từ 0 đến M5:
* F[i][j]=max(F[i][j], F[i-1][j-P5[x]]+P2[x]);

Cách tìm đáp án:
* kq=0;
* Với mỗi j chạy từ 0 đến M5:
* T=min(j, F[k][j]);
* kq=max(kq, T);
* Viết kq;

Với M5 = sum(P5[1..n])

{%hackmd AfkxoUIBRFKjyvpLo0GIFg %}

[.](https://www.geeksforgeeks.org/maximum-number-of-trailing-zeros-in-the-product-of-the-subsets-of-size-k/)

[Code c++ #1](https://hackmd.io/@hoclentop/HJqwCwH2i)