修改数组里的值,使数组(不严格)单调,且改动最小。
考虑动态规划。
上升和下降的方法都是一样的,以上升为例。
当修改一个数时,一定会把它修改成数组中出现过的某一个数。
那么把数组离散化一下,$b[i]$表示数组中第$i$大的数(这里可以用unique去重一下)。
那么只要枚举将每个数修改成其他数,且前面的数≤这个数时的最小值就可以了。
但是每次枚举这个数之前的所有数的情况会很多,所以每枚举一位要把最小值处理出来。
设$f[i][j]$为当前枚举到第$i$位,前$i$位的值都不超过$b[j]$时,修改的最小值。
如果把$a[i]$修改为$b[j]$,则总花费为$abs(a[i]-b[j])$+之前$i-1$位的花费$f[i-1][j]$。
如果前$i$个数都不超过$b[j-1]$,则也一定不超过$b[j]$,那么前$i$位的值都不超过$b[j]$的最小花费,也可以从前$i$位的值都不超过$b[j-1]$的最小花费转移过来。
则状态转移方程为$f[i][j] = min(f[i-1][j]+abs(a[i]-b[j]),f[i][j-1])$
f[i][j] = abs(a[i]-b[j]); if(i > 1) f[i][j] += f[i-1][j]; f[i][j] = min(f[i][j],f[i][j-1]);
完整代码如下
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define MogeKo qwq #include<algorithm> using namespace std; const int maxn = 2010; const int INF = 0x3f3f3f3f; int n,m,ans,a[maxn],b[maxn],f[maxn][maxn]; void init() { for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) f[i][j] = INF; } void dp() { init(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { f[i][j] = abs(a[i]-b[j]); if(i > 1) f[i][j] += f[i-1][j]; f[i][j] = min(f[i][j],f[i][j-1]); } } int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); b[i] = a[i]; } sort(b+1,b+n+1); m = unique(b+1,b+n+1)-b-1; dp(); ans = f[n][m]; sort(b+1,b+m+1,greater<int>()); dp(); ans = min(ans,f[n][m]); printf("%d",ans); return 0; }View Code