CF1525D Armchairs 题解

· · 题解

解题方法

这道题是一个匹配的问题，这个经典问题可以用排序来解决。

那么我们可以考虑枚举 a_i=0 参与匹配的集合 S，然后依次匹配即可。

设 dp[i][j] 表示考虑到 i 已经匹配了 j 个 1 的最小花费，转移后就可以达到 O(n^2)。