题目链接

解题思路

本题有一个引理：在满足 S 最小化的前提下，一定存在一种构造序列 B 的方案，使得 B 中的数值都在 A 中出现过。
若想证明，请看《算法竞赛进阶指南》268 页。
如果去掉之前的推论，那么只有绿题难度。

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int a[2005],b[2005];
int dp[2005][2005];//dp[i][j]代表排序1-i后，a[i]=b[j]的最小s
bool cmp(int a,int b){
    return a>b;
}
int 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);//b记录a的排序结果
    int minn=inf;
    int minpos=0;
    int minsum=0;
    int last=unique(b+1,b+1+n)-b-1; 
    for(int i=1;i<=n;i++){
        minn=inf;
        for(int j=1;j<=last;j++){
            if(minn>dp[i-1][j]){
                minn=dp[i-1][j];
                minpos=j;
            }
//当前状态从上一次的状态+从a[i]到b[j]的改变的值
            dp[i][j]=dp[i-1][minpos]+abs(a[i]-b[j]);//由于在之前取状态时的j小于现在的j，b[minpos]<b[j]。
        }
    }
    int ans=inf;
    for(int i=1;i<=last;i++){
        ans=min(ans,dp[n][i]);
    }
//以上是上升，以下是下降
    sort(b+1,b+1+last,cmp);
    for(int i=1;i<=n;i++){
        minn=inf;
        for(int j=1;j<=last;j++){
            if(minn>dp[i-1][j]){
                minn=dp[i-1][j];
                minpos=j;
            }
            dp[i][j]=dp[i-1][minpos]+abs(a[i]-b[j]);
        }
    }
    for(int i=1;i<=last;i++){
        ans=min(ans,dp[n][i]);
    }
    cout<<ans;
    return 0;
}