Hướng dẫn giải của Free Contest 140 - DIVA
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Gọi ~dp_{i, j}~ là chi phí thấp nhất khi xét đến phần tử thứ ~i~ có giá trị ~j~ thỏa dãy ~a_{1}, ... a_{i}~ có ~a_{k + 1}~ chia hết ~a_{k}~ với ~1 \le k < i~.
~dp_{i, k} = min(dp_{i, k}~, ~dp_{i, j} + |a_{i} - k|)~ với ~k~ chia hết cho ~j~.
DPT: ~O(2\times n^2 \times (1 + \frac{1}{2} + ... + \frac{1}{n}))~
Bình luận