本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-21 16:08:25

题目描述

给定一个序列，每次操作可以把某个数加上 $1$ 或减去 $1$。要求把序列变成非降数列。最小化操作次数。

我们发现，要把一个数列改成一个非严格递增的数列，要么这个数还是自己，要么这个数就是前面一个数，不然总不是最优的，可以手动模拟看一看。

此题显然用DP。

我们设 $f_{i,j}$ 为第 $i$ 位放 $j$ 时的最小花费。

根据前面的推导，我们将 $a$ 数组从小到大排序记为 $b$ 数组，则$f_{i,j}$ 为第 $i$ 位放 $b_j$ 时的最小花费。

显然可推出状态转移方程

$$f_{i,j}=(f_{i-1,k})_{min}+|a_i-b_j|$$

其中 $k$ 从数组的最小值遍历到最大值。

我们可以再用一个数组 $mi_{i,j}$ 来计算 $min(f_{i,k})$

$$mi_{i,j}=min(mi_{i,j-1},f_{i,j})$$

状态转移方程为：

$$f_{i,j}=mi_{i-1,j}+|a_i-b_j|$$

提交之后就MLE了。

我们发现，$f$ 只和 $f_{i-1}$ 和 $f_i$ 有关系，所以我们可以用滚动数组优化DP。

$f_{i-1}$ 为 $f_0$，$f_i$ 为 $f_1$。

则最终的状态转移方程为：

$$f_{1,j}=min(f_{1,j-1},f_{0,j}+|a_i-b_j|)$$

注：此时可以将 $mi$ 数组和 $f$ 数组合并，原本的状态转移方程为：

$$mi_{1,j}=min(mi_{1,j-1},ff)$$

$$ff=mi_{0,j}+|a_i-b_j|$$

所以就AC了

代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=5005;
int a[N];
int f[2][N];
int b[N];
int n,m;
signed main(){
    int  n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        f[1][0]=1e18;
        for(int j=1;j<=n;j++){
            f[1][j]=min(f[1][j-1],f[0][j]+abs(a[i]-b[j]));
        }
        for(int j=1;j<=n;j++) f[0][j]=f[1][j];
        
    }
    cout<<f[1][n];
    return 0;
}