CF13C 题解
__S08577__
·
·
题解
题目描述
给定一个序列，每次操作可以把某个数加上 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_{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了
## 代码
```cpp
#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;
}
```