题解： B[i]的值肯定是A[i]的值的某一个，将A[i]sort一下 F[i][j]表示 处理道第i个A[i] 以sort完后的新数组来说 B[j]结尾的最小花费。
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<vector> 4 #include<queue> 5 #include<map> 6 #include<iostream> 7 #include<cstring> 8 using namespace std; 9 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 10 #define LL long long 11 #define ULL unsigned LL 12 #define fi first 13 #define se second 14 #define pb push_back 15 #define lson l,m,rt<<1 16 #define rson m+1,r,rt<<1|1 17 #define lch(x) tr[x].son[0] 18 #define rch(x) tr[x].son[1] 19 #define max3(a,b,c) max(a,max(b,c)) 20 #define min3(a,b,c) min(a,min(b,c)) 21 typedef pair<int,int> pll; 22 const int inf = 0x3f3f3f3f; 23 const LL INF = 0x3f3f3f3f3f3f3f3f; 24 const LL mod = (int)1e9+7; 25 const int N = 2e3 + 100; 26 int a[N], b[N]; 27 LL F[N][N]; 28 int main(){ 29 int n; 30 scanf("%d", &n); 31 for(int i = 1; i <= n; ++i) 32 scanf("%d", &a[i]), b[i] = a[i]; 33 sort(b+1, b+1+n); 34 35 for(int i = 1; i <= n; i++){ 36 LL mn = INF; 37 for(int j = 1; j <= n; j++) F[i][j] = INF; 38 for(int j = 1; j <= n; j++){ 39 mn = min(mn, F[i-1][j]); 40 F[i][j] = min(F[i][j], mn + abs(a[i]-b[j])); 41 } 42 } 43 LL ans = INF; 44 for(int j = 1; j <= n; j++) ans = min(F[n][j], ans); 45 for(int i = 1; i <= n; i++){ 46 LL mn = INF; 47 for(int j = 1; j <= n; j++) F[i][j] = INF; 48 for(int j = n; j >= 1; j--){ 49 mn = min(mn, F[i-1][j]); 50 F[i][j] = min(F[i][j], mn + abs(a[i]-b[j])); 51 } 52 } 53 for(int j = 1; j <= n; j++) ans = min(F[n][j], ans); 54 printf("%lld ", ans); 55 return 0; 56 }