题目大意

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

解题思路

看完题解后发现是 dp 。想想如何想到 dp 。

题目特地给了个貌似没用的 $ m $ ，这应该是给了这题要用 $ dp $ 的提示。

设 $ 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);
}