CF1675G Sorting Pancakes

· · 题解

首先，可以感性地发现挪馅饼时出现负值不会影响最终答案，只要最终方案是非负的就行了。

所以，我们不妨规定，一个盘子只能从右边一个盘子拿馅饼，或者向右边一个盘子放馅饼。

我们用 f_{i,j,k} 表示前 i 盘放 j 张馅饼，第 i 盘放 k 张馅饼的最小花费。不难发现 f_{i,j,k} 可以转移到 f_{i+1,j+p,p} 。

现在我们记原来前 i 个盘子上的馅饼和为 S_i 。

考虑如何从 f_{i,j,k} 转移到 f_{i+1,j+p,p} ：由于我们每次转移馅饼都只和右边一个盘子有关，所以前 i 个盘子定好后的状态中，前 i+1 个盘子上的馅饼数之和依然是 S_{i+1} 。

所以我们只需从第 i+2 个盘子里拿 j+p-S_{i+1} 个馅饼到第 i+1 个盘子上就行了（若拿负数个馅饼过来，等同于拿出去这么多个）。于是状态转移方程就推出来了：

f_{i+1,j+p,p} = min\{f_{i+1,j+p,p},f_{i,j,k}+\mid j+p-S_{i+1}\mid\}

枚举 i,j,k,p ，复杂度 O(n\times m^3) ，会超时。

考虑到 f_{i+1,j+p,p} 会被所有 f_{i,j,k}(k\geq p) 都转移一次，故可以倒着枚举 k ：设当前枚举到 i,j,k ， minn = min_{h=k}^m f_{i,j,h} ，则有转移方程：

f_{i+1,j+k,k} = min\{ minn + \mid j+p-S_{i+1}\mid\}

最终答案 ans 为：

ans = min_{k=0}^{m}\{ f_{n,m,k}\}

时间复杂度 O(n\times m^2) ，可以通过此题。

代码