题意：
给定一个长度为n的序列A，构造一个长度为n的序列B，满足b非严格单调，并且最小化S=∑i=1N |Ai-Bi|，求出这个最小值S,1<=N<=2000,1<=Ai<=1e9.
引理：在满足S最小化的情况下，一定存在一种构造序列B的方案，使得B中的数值都在A中出现过。
由此，用一个数组b[i]初始化=a[i]，然后对b从小到大排序，用f[i][j]表示完成了B中前i个数的构造，第i个数为b[j]时的最小的S.当第i个数等于b[j]时，因为B序列是单调递增的，所以之前构造的数一定在b[1]~b[j]之间，用tmp维护其最小值即可，则有：
for(res i=1 ; i<=n ; i++) { LL tmp=f[i-1][1]; for(res j=1 ; j<=n ; j++) { tmp=min(tmp,f[i-1][j]); f[i][j]=tmp+abs(a[i]-b[j]) } }
最后答案即为f[1~n]的最小值。
进一步优化：
发现第一维可以省略掉。
完整代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 #define INF (2147483640) 8 const int N=4000+100; 9 int a[N],b[N]; 10 int f[N],n; 11 12 int main() 13 { 14 scanf("%d",&n); 15 for(int i=1 ; i<=n ; i++) scanf("%d",&a[i]),b[i]=a[i]; 16 17 sort(b+1,b+n+1); 18 int ans=INF; 19 for(int i=1 ; i<=n ; i++) 20 { 21 int t=INF; 22 for(int j=1 ; j<=n ; j++) 23 { 24 t=min(t,f[j]); 25 f[j]=abs(b[j]-a[i])+t; 26 } 27 } 28 for(int i=1 ; i<=n ; i++) 29 ans=min(ans,f[i]); 30 printf("%d\n",ans); 31 return 0; 32 } 33
原文：https://www.cnblogs.com/wmq12138/p/10364327.html
