Educational Codeforces Round 109 Armchairs 题解(Java/C++)

题意

有n个板凳，有不超过$\frac{n}{2}$个人已经坐在上面，现在每次你可以让任意一个人坐到另外一个空位上，开销是两个空位的下标的差。问你，把这些人挪了之后，所有之前坐了人的空位都不坐人的最小开销。

题解

定义dp[i][j]表示第i个1，改换到第j个0所需要的最小开销。显然有： $$dp[i][j]=\min\limits_{i-1\leq x <j }(dp[i-1][x])+|index(1,i) - index(0,j)|$$
其中$index(x,i)$表示第i个$a=x$的下标。比如，$index(0,1)=4$，则$a_4$是第1个0，也就是$a_0=...=a_3=1$。

最终结果就是$\min\limits_{count[1]-1\leq x < count[0] }(dp[count[1]-1][x])$。

代码

Java

C++