题目大意
有 $ n $ 个箱子和 $ m $ 个小球,初始时第 $ i $ 个箱子有 $ a_i $ 个小球。每次操作可以将一个小球移到相邻的箱子里。求要使得最终数组 $ a_i \ge a_{i+1} $的最小操作次数。
解题思路
设$ dp_{i,j,k} $ 为前 $ i $ 个箱子里一共放 $ j $ 个球,第 $ i $ 个箱子里放 $ k $ 个小球的代价。
我们先维护一个前缀和数组 $s_i$,然后在进行操作,例如:
原数组$ 5 \ 3 \ 2 \ 3 \ 3 \ 3 \ 3$
前缀和$ 5 \ 8 \ 10 \ 13 \ 16 \ 19 \ 21 $
显然我们要将第二个盒子的小球放入第三个小球中,更改后:
原数组$ 5 \ 2 \ 3 \ 3 \ 3 \ 3 \ 3$
前缀和$ 5 \ 7 \ 10 \ 13 \ 16 \ 19 \ 21$
我们可以发现,移动了小球后只有给出小球的一方前缀和会发生变化,其他则不受影响。因此,移动一个小球的代价即为 $ | s_i – j | $(即下标为 $ i $ 的箱子中的小球的前后变化的数量), $ j $ 的含义与上文相同。
怎么计算代价已经明了了,接下来就可以考虑状态转移方程了。
$$
dp_{i,j,k} = \min_{l=k}^m ( dp_{i,j,k} , dp_{i-1,j-k,l} + | s_i – j |)
$$
由于目的是构建非严格单调递减,所以 $ k \leq l \leq m $ ,这样子的时间复杂度是 $ O(NM^3) $ ,大概是可以过这一题的,但我们还可以进行进一步的优化。
我们可以发现在状态转移方程中有一个不变的量 $ | s_i – j | $ ,唯一变的量是 $ dp_{i-1,k,l} $ ,因为是找最小,所以我们只要提前维护好 $ dp_{i-j,k,l} $ 的最小值即可。时间复杂度为 $ O(NM^2) $
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(1)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <math.h>
using namespace std;
const int N=250+10;
int n,m;
int a[N],s[N];
int dp[2][N][N];//滚动数组节省内存
int g[2][N][N];
int ans;
inline int read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++){
a[i]=read();
s[i]=s[i-1]+a[i];
}
memset(dp,0x3f,sizeof dp);
for(int i=0;i<=m;i++)dp[0][0][i]=0;
for(int i=1;i<=n;i++){
int id=i&1;
memset(dp[id],0x3f,sizeof dp[id]);
memset(g[id],0x3f,sizeof g[id]);
for(int j=0;j<=m;j++){
for(int k=0;k<=j;k++){
dp[id][j][k]=g[id^1][j-k][k]+abs(s[i]-j);
}
}
for(int j=0;j<=m;j++){
for(int k=j;k>=0;k--){
g[id][j][k]=min(g[id][j][k+1],dp[id][j][k]);
}
}
}
ans=0x3f3f3f3f;
for(int i=0;i<=m;i++){
ans=min(ans,dp[n&1][m][i]);
}
printf("%d",ans);
}