#动态规划#poj 3666 洛谷 2893 修路 Making the Grade

本文主要是介绍#动态规划#poj 3666 洛谷 2893 修路 Making the Grade，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给出一个长度是$n$的序列$A$，构造出一个长度为$n$的单调不递减序列$B$，使${\sum }_{i=1}^{n}abs(A[i]-B[i])$最小

---

分析

设$f[i][j]$表示完成前$i$个数的构造，其中$j=B[i]$时的答案的最小值
f [ i ] [ j ] = m i n { f [ i − 1 ] [ k ] + ∣ A [ i ] − j ∣ } f[i][j]=min\{f[i-1][k]+|A[i]-j|\} f[i][j]=min{f[i−1][k]+∣A[i]−j∣}
然而由于$A$可以离散，所以时间降到$O(n^2)$

---

代码

#include <cstdio>
#include <algorithm>
int n,a[2001],b[2001],f[2001];
int in(){int ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
int abs(int x){return (x<0)?-x:x;}
int min(int a,int b){return (a<b)?a:b;}
int main(){n=in();for (int i=1;i<=n;i++) b[i]=a[i]=in();std::stable_sort(b+1,b+1+n);//快排（离散）for (int i=1;i<=n;i++){long long minx=f[1];//找最小值for (int j=1;j<=n;j++){minx=min(minx,f[j]);f[j]=abs(a[i]-b[j])+minx;//那么如果选定答案就是差值+最小值}}int ans=f[n];for (int i=1;i<n;i++) ans=min(ans,f[i]);return !printf("%d",ans);
}

这篇关于#动态规划#poj 3666 洛谷 2893 修路 Making the Grade的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---