嗯……这题是做两遍dp,设f[i][j]为前i个点的路面当高度为j(已经离散化)后所能付出的最小代价，则状态转移方程为：
f[i][j]=min(f[i][j-1],f[i-1][j]+abs(j-a[i]))
我作死用了滚动数组……
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[2005],f[2][2005],g[2][2005],b[2005];
int absd(int h){
return h>0?h:-h;
}
int cmp(int sa,int sb){
return sa>sb;
}
int main(){
freopen("1592.in","r",stdin);
freopen("1592.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
f[1][0]=f[0][0]=2147483647;
for(int i=1;i<=n;i++){
int now=i%2,pre;
pre=now^1;
for(int j=1;j<=n;j++){
f[now][j]=min(f[now][j-1],f[pre][j]+absd(b[j]-a[i]));
}
}
g[0][0]=g[1][0]=2147483647;
for(int i=1;i<=n;i++){
int now=i%2,pre;
pre=now^1;
for(int j=1;j<=n;j++){
g[now][j]=min(g[now][j-1],g[pre][j]+absd(b[n+1-j]-a[i]));
}
}
printf("%d\n",min(g[n%2][n],f[n%2][n]));
return 0;
}
评论 (0)
