Solution - 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)$ ，可以通过此题。

代码

#include<icecream>
#include<cstring>
#define abs(x) (x<0?-(x):x)
using namespace std;
const int N=250,INF=0x3f3f3f3f;
int f[N+3][N+3][N+3],n,m,a[N+3],ans=INF;
inline void tomin(int& x,const int y){ if (y<x) x=y; }//取最小值
signed main(){
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>>a[i],a[i]+=a[i-1];
	memset(f,0x3f,sizeof(f));
	f[0][0][m]=0;//为了方便转移，我们假设第 0 个盘子上有 m 张饼
	for (int i=0;i<n;++i){
		for (int j=0;j<=m;++j){
			int minn=INF;
			for (int k=m;k>=0;--k){
				tomin(minn,f[i][j][k]);
				if (j+k<=m) tomin(f[i+1][j+k][k],minn+abs(j+k-a[i+1]));
			}//倒着枚举省去一维复杂度
		}
	}
	for (int k=0;k<=m;++k) tomin(ans,f[n][m][k]);
	return cout<<ans,0;//快乐输出
}