我们钦定\(a\)中一些数字是选定点，及保证他们不与零球交换，首先容易发现这些选定点一定是单调递增的。因此\(0\)球个数就是未选定点的连续段个数，而交换次数就是未选定点的个数
因此我们考虑判断每个球选定不选定：设\(dp_{i,j}\)表示前\(i\)个球中用了最多\(j\)个\(0\)球，\(i\)球必须选，最少交换次数
容易得到递推式，这里不放了
最终复杂度\(O(n^3)\)
CF1839D Ball Sorting
发布时间 2023-09-18 18:41:44作者: FOX_konata