CF1675G Sorting Pancakes 做题记录

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

1n,m2501\le n,m\le 250

aa 反过来,问题变成了让 aiai1a_i\ge a_{i-1} 的最小操作次数。

考虑设 dpi,j,kdp_{i,j,k} 为前 i1i-1 个满足条件,ai=ja_i=jaiai1=ka_i-a_{i-1}=k 的最小操作次数,并且 ii 后面的位置没有改动。这么设置状态是因为 aia_i 不会影响到 ai2a_{i-2},而 ai1a_{i-1}ai2a_{i-2} 的影响已经算过了,实现了无后效性。

显然有 dp1,a1,a1=0dp_{1,a_1,a_1}=0

考虑转移,按 jjaia_i 的大小关系分类:

  • j>aij>a_i:多出来的只可能是 ai1a_{i-1} 给的,此时 aia_i 肯定没给 ai1a_{i-1},所以 dpi,j,k=jai+minl=jaimdpi1,jk+jai,ldp_{i,j,k}=j-a_i+\min\limits_{l=j-a_i}^{m}dp_{i-1,j-k+j-a_i,l}
  • j<aij<a_i:少掉的只可能是给了 ai1a_{i-1},此时 ai1a_{i-1} 肯定没给 aia_i。并且注意到因为给了 ai1a_{i-1} 一些,所以 ai1a_{i-1} 在没给之前可以比 ai2a_{i-2} 小,也就是说 dpi,j,k=aij+minl=jaimai+jdpi1,jkai+j,ldp_{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=aij=a_i:谁也没给谁,dpi,j,k=minl=0mdpi1,jk,ldp_{i,j,k}=\min\limits_{l=0}^{m}dp_{i-1,j-k,l}

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

注意到转移中的 min\min 可以用后缀 min\min 来优化到 O(1)O(1),那么可以在 O(nm2)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;
}