【题解】分级
题目链接
解题思路
本题有一个引理:在满足 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;
}