问题描述
题解
对于(A)中的每一个元素,都将存在于(B)中。
对(A)离散化。
设(opt_{i,j})代表([1,i]),结尾为(j)的最小代价。
[opt_{i,j}=min_{k in [1,m]} {opt_{i-1,k}+ |a_i-k|}
]
(mathrm{Code})
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
void read(int &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') ch=getchar(),fh=-1;
else fh=1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=fh;
}
const int maxn=2000+7;
const int INF=0x3f3f3f3f;
int m,n,b[maxn],a[maxn],c[maxn];
int opt[maxn][maxn];
int ans=INF;
void preprocess(){
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);b[i]=a[i];
}
memset(opt,0x3f,sizeof(opt));
preprocess();
opt[0][0]=0;
for(int i=1;i<=n;i++){
int val=opt[i-1][0];
for(int j=1;j<=m;j++){
val=min(val,opt[i-1][j]);
opt[i][j]=val+abs(a[i]-b[j]);
}
}
for(int i=1;i<=m;i++) ans=min(ans,opt[n][i]);
printf("%d
",ans);
return 0;
}