有 个箱子和 个小球,初始时第 个箱子有 个小球。每次操作可以将一个小球移到相邻的箱子里。求要使得最终数组 的最小操作次数。
。
把 反过来,问题变成了让 的最小操作次数。
考虑设 为前 个满足条件, 且 的最小操作次数,并且 后面的位置没有改动。这么设置状态是因为 不会影响到 ,而 对 的影响已经算过了,实现了无后效性。
显然有 。
考虑转移,按 和 的大小关系分类:
- :多出来的只可能是 给的,此时 肯定没给 ,所以 ;
- :少掉的只可能是给了 ,此时 肯定没给 。并且注意到因为给了 一些,所以 在没给之前可以比 小,也就是说 ;
- :谁也没给谁,。
最后答案即为 。
注意到转移中的 可以用后缀 来优化到 ,那么可以在 的时间复杂度内解决此题。
完整代码:
// 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;
}