Editorial for Bedao Regular Contest 12 - BFRIDAY


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Từ đề bài, ta có thể thấy: một dãy số dễ thương cần đáp ứng đủ ~2~ điều kiện sau: ~\displaystyle\sum_{i=0}^{k-1}a_i\equiv 0\;(\text{mod }2)~ và ~a_i\equiv a_{i-k}\;(\text{mod }2)~, hay nói cách khác, nếu ~p_i\equiv p_j\;(\text{mod }k)~ thì ~a_{p_i}\equiv a_{p_j}\;(\text{mod }2)~.

Ta có thể giải bài toán trên bằng quy hoạch động: gọi ~dp[i][j]~ là số bước thay đổi ít nhất cho ~i~ nhóm đồng dư đầu tiên của ~k~, sao cho tổng của các số đã được xét sẽ đồng dư ~j~ theo mod ~2~.

Ta được công thức quy hoạch động sau: ~dp[i][j] = \text{min}(dp[i - 1][j] + cnt[i][1], dp[i - 1][1 - j] + cnt[i][0])~ với ~cnt[i][j]~ là số vị trí ~p~ thỏa ~p\equiv i\;(\text{mod }k)~ và ~a_{p}\equiv j\;(\text{mod }2)~.

Độ phức tạp: ~O(n)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.