Educational Codeforces Round 109 Armchairs Solution (Java/C++)

Solution:

Define dp[i][j] to stand for the minimum cost if we move the people from the i th occupied armchair to j-th empty armchair. And $$dp[i][j]=\min\limits_{i-1\leq x <j }(dp[i-1][x])+|index(1,i) - index(0,j)|$$
$index(x,i)$ is the i-th index which $a=x$. For example, $index(0,1)=4$, then $a_4$ is the first zero. And $a_0=...=a_3=1$.

So, the answer is: $\min\limits_{count[1]-1\leq x < count[0] }(dp[count[1]-1][x])$.

Code:

Java

C++