【算法】动态规划DP
【题解】
题目要求不严格递增或不严格递减。
首先修改后的数字一定是原来出现过的数字，这样就可以离散化。
f[i][j]表示前i个，第i个修改为第j个数字的最小代价，a表示排序后数组，b表示原数组。
f[i][j]=min(f[i-1][k])+abs(b[i]-a[j])
min部分优化，复杂度O(n^2)。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=,inf=0x3f3f3f3f;
int f[maxn][maxn],n,a[maxn],num,b[maxn];
bool cmp(int a,int b){return a>b;}
int abs(int x){return x>?x:-x;}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(a+,a+n+);
f[][]=;
for(int i=;i<=n;i++){
num=inf;
for(int j=;j<=n;j++){
num=min(num,f[i-][j]);
f[i][j]=num+abs(b[i]-a[j]);
}
}
int ans=inf;
for(int i=;i<=n;i++)ans=min(ans,f[n][i]);
memset(f,,sizeof(f));
sort(a+,a+n+,cmp);
for(int i=;i<=n;i++){
num=inf;
for(int j=;j<=n;j++){
num=min(num,f[i-][j]);
f[i][j]=num+abs(b[i]-a[j]);
}
}
for(int i=;i<=n;i++)ans=min(ans,f[n][i]);
printf("%d",ans);
return ;
}
和【CH】整洁的麻将桌差不多。