【算法】动态规划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
      
       #include
       
        #include
        
         using namespace std;const int maxn=2010,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>0?x:-x;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];    sort(a+1,a+n+1);    f[0][0]=0;    for(int i=1;i<=n;i++){        num=inf;        for(int j=1;j<=n;j++){            num=min(num,f[i-1][j]);            f[i][j]=num+abs(b[i]-a[j]);        }    }    int ans=inf;    for(int i=1;i<=n;i++)ans=min(ans,f[n][i]);    memset(f,0,sizeof(f));    sort(a+1,a+n+1,cmp);    for(int i=1;i<=n;i++){        num=inf;        for(int j=1;j<=n;j++){            num=min(num,f[i-1][j]);            f[i][j]=num+abs(b[i]-a[j]);        }    }    for(int i=1;i<=n;i++)ans=min(ans,f[n][i]);    printf("%d",ans);    return 0;}
        
       
      

和差不多。