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

Submission #116469792 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #116470381 - Codeforces
Codeforces. Programming competitions and contests, programming community
蜀ICP备19018968号