warning:此方法可能较难理解 讲的烂
约定
-
除去标有“移动”，所有的 (A) 都为原始输入顺序。
-
(i ext{~}j) 的“代价”定义为 (sum_{k=i}^{j-1}|A_k-A_{k+1}|) .
思路
这种题比较明显的是DP，有两种解法。我果然选择了空间更差不能优化的顺推法
首先，由于交换的位置从前往后，所以一个数要么向前移动1位，要么向后移动若干位（包括0）
用不加调料的脑回路设状态：
假设 (A_i) 向后移动，那么 (A_{i-1}) 与 (A_{i}) 肯定没有交换。明显的，对于 (i) 固定的情况下，能转移的前置 (F) 一定是固定的，为 (F_{k,i-1}phantom{1}(k<i)) 。同时，因为第 (i-1) 个数（(A_k)）和第 (i) 个数（注意是 (A_{i+1})，(A_i) 被换出去了）是确定的，所以移动后 (1 ext{~}i) 的代价是固定的，可以以 (O(N)) 的时间复杂度计算。
然后，对于移动后 (i ext{~}j) 的代价，因为只有 (A_i) 在移动，所以 (A_{i+1} ext{~}A_j) 的相对位置是不变的，于是移动后 (i+1 ext{~}j) 的代价当然也是不变的，可以预先用一个 (S) 数组 (O(n^2)) 预处理每个区间的代价。在此基础上，再加上 (|A_i-A_j|) ，就是移动后 (i ext{~}j) 的代价。
那么，我们可以列出一条式子：
（(S_{i,j}) 表示原来中 (i ext{~} j)的代价）
对于 (min) 函数内的部分，就是之前提到可以预处理的部分。
我们要注意到这条式子有一个限制条件：((i<j)) ，因为我们假定 (A_i) 移动。
对于不移动的情况，我们只需要考虑前置 (F) 和结尾与 (A_i) 的差即可：
(注意 (min) 函数里面的差别)
那么，最后的答案就是枚举一下谁在最后，即：
实现
注意对于 (i=1) 时，(F_{i,i}) 和 (min{{F_{k,i-1}+|A_{i+1}-A_k|}}) 的值为0，由于不会被转移，需要特殊处理。
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,ans=0x7fffffff,a[2010],s[2010][2010],f[2010][2010];
void read(int &x){
char c=getchar();
for(;c<33;c=getchar());
for(x=0;(c>47)&&(c<58);x=x*10+c-48,c=getchar());
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
s[i][j]=s[i][j-1]+abs(a[j]-a[j-1]);
}
}
for(int i=1;i<=n;i++){
int temp=f[i][i]=i==1?0:0x7fffffff;
for(int j=1;j<i;j++){
temp=min(temp,f[j][i-1]+abs(a[i+1]-a[j]));
f[i][i]=min(f[i][i],f[j][i-1]+abs(a[i]-a[j]));
}
for(int j=i+1;j<=n;j++){
f[i][j]=temp+abs(a[i]-a[j])+s[i+1][j];
}
}
for(int i=1;i<=n;i++){
ans=min(ans,f[i][n]);
}
printf("%d",ans);
}