CF1675G Sorting Pancakes 做题记录

有 $n$ 个箱子和 $m$ 个小球，初始时第 $i$ 个箱子有 $a_i$ 个小球。每次操作可以将一个小球移到相邻的箱子里。求要使得最终数组 $a_i\ge a_{i+1}$ 的最小操作次数。

$1\le n,m\le 250$。

把 $a$ 反过来，问题变成了让 $a_i\ge a_{i-1}$ 的最小操作次数。

考虑设 $dp_{i,j,k}$ 为前 $i-1$ 个满足条件，$a_i=j$ 且 $a_i-a_{i-1}=k$ 的最小操作次数，并且 $i$ 后面的位置没有改动。这么设置状态是因为 $a_i$ 不会影响到 $a_{i-2}$，而 $a_{i-1}$ 对 $a_{i-2}$ 的影响已经算过了，实现了无后效性。

显然有 $dp_{1,a_1,a_1}=0$。

考虑转移，按 $j$ 和 $a_i$ 的大小关系分类：

• $j>a_i$：多出来的只可能是 $a_{i-1}$ 给的，此时 $a_i$ 肯定没给 $a_{i-1}$，所以 $dp_{i,j,k}=j-a_i+\min\limits_{l=j-a_i}^{m}dp_{i-1,j-k+j-a_i,l}$；
• $j<a_i$：少掉的只可能是给了 $a_{i-1}$，此时 $a_{i-1}$ 肯定没给 $a_i$。并且注意到因为给了 $a_{i-1}$ 一些，所以 $a_{i-1}$ 在没给之前可以比 $a_{i-2}$ 小，也就是说 $dp_{i,j,k}=a_i-j+\min\limits_{l=j-a_i}^{m-a_i+j} dp_{i-1,j-k-a_i+j,l}$；
• $j=a_i$：谁也没给谁，$dp_{i,j,k}=\min\limits_{l=0}^{m}dp_{i-1,j-k,l}$。

最后答案即为 $\min\limits_{i=0}^m\min\limits_{j=0}^idp_{n,i,j}$。

注意到转移中的 $\min$ 可以用后缀 $\min$ 来优化到 $O(1)$，那么可以在 $O(nm^2)$ 的时间复杂度内解决此题。

完整代码：

// Problem: CF1675G Sorting Pancakes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1675G
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
const long long MS=255;
const int mov=252,mov2=502;
 
int n,m,a[MS];
int dp[2][MS*3][MS*3],mn[2][MS*3][MS*3];
 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n/2;i++)
	{
		swap(a[i],a[n-i+1]);
	}
	memset(dp,127,sizeof(dp));
	memset(mn,127,sizeof(mn));
	dp[1][a[1]+mov][a[1]+mov2]=0;
	for(int i=m;i>=-m*2;i--)
	{
		int id1=a[1]+mov;
		int id2=i+mov2;
		mn[1][id1][id2]=min(mn[1][id1][id2+1],dp[1][id1][id2]);
	}
	for(int i=2;i<=n;i++)
	{
		int u=i&1;
		int v=u^1;
		memset(dp[u],127,sizeof(dp[u]));
		memset(mn[u],127,sizeof(mn[u]));
		for(int j=-m;j<=m;j++)
		{
			int idj=j+mov;
			for(int k=j-m;k<=j;k++)
			{
				int idk=k+mov2;
				if(j>a[i])
				{
					dp[u][idj][idk]=j-a[i]+mn[v][j-k+j-a[i]+mov][j-a[i]+mov2];
				}
				else if(j<a[i])
				{
					dp[u][idj][idk]=a[i]-j+mn[v][j-k+j-a[i]+mov][j-a[i]+mov2];
				}
				else
				{
					dp[u][idj][idk]=mn[v][j-k+mov][mov2];
				}
			}
			for(int k=m;k>=-m*2;k--)
			{
				int idk=k+mov2;
				mn[u][idj][idk]=min(mn[u][idj][idk+1],dp[u][idj][idk]);
			}
		}
	}
	int ans=1e8;
	for(int i=0;i<=m;i++)
	{
		ans=min(ans,mn[n&1][i+mov][mov2]);
	}
	printf("%d\n",ans);
	return 0;
}