很直接的想法是枚举每个二进制状态，并比较得出最小值，期望得分20分。
但是我们可以从数据范围看出这是一个二维dp （不要问我是怎么看出来的） 。考场尚未推出状态转移方程，考后参考别人的程序才想出，这其实是一道dp好题。
定义f[
][0]为第
个值不与后面的交换消耗的最小体力，f[
][1]为第
个值与后面交换消耗的最小的最小体力，sum[
]为未交换时消耗的体力。
状态转移方程：
1.当第
个值不与后面的值交换时，此时消耗的最小体力就是
(第
个值不与后面交换时的最小体力加上第
个值与
个值的差值的绝对值，
第
个值与后面交换时的最小体力加上第
个值与
个值的差值的绝对值)。
code:
f[i][0]=min(f[i+1][0]+abs(a[i+1]-a[i]),f[i+1][1]+abs(a[i+2]-a[i]));
2.当第
个值与后面的值交换时，此时消耗的最小体力就与第
个值具体被换到哪里有关。设第
个值与第
个值交换，此处较难理解，用图片具体说明：
i与j交换前：
i与j交换后：
这里简单地用
表示a[
]的值（其他依次类推）。设第
个位置的值与第
个位置的值交换，交换后消耗的最小体力其实就是a[
]与a[
]的差值的绝对值加上第
个位置和第
个位置中间的差值再加上一个类似于f[
][0]的式子，只是这里因为原来a[
]的位置现在是a[
],所以将f[
][0]式子中的
换成
。特别的，与第
个值交换，因为f[
][0]和f[
][1]都是0，所以f[
][0]可直接由a[
]与a[
]的差值的绝对值加上第
个位置和第
个位置中间的差值得到。
code:
for(ll j=i+1;j<=n-1;j++)f[i][1]=min(f[i][1],min(f[j+1][0]+abs(a[i]-a[j+1]),f[j+1][1]+abs(a[i]-a[j+2]))+sum[j]-sum[i+1]+abs(a[i]-a[j]));
f[i][1]=min(f[i][1],sum[n]-sum[i+1]+abs(a[n]-a[i]));
完整code:
#include<bits/stdc++.h>
#define ll long long
#define R register
using namespace std;
inline ll read(){ll f=0,pa=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')pa=-1;ch=getchar();}while(ch>='0'&&ch<='9'){f=(f<<3)+(f<<1)+(ch^48);ch=getchar();}return f*pa;
}
inline void write(ll x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');
}
ll n,a[2005],sum[2005],f[2005][2],cha;
inline ll abss(ll a){return a>=0?a:-a;}
inline ll minn(ll a,ll b){return a>b?b:a;}
int main(){n=read();for(R ll i=1;i<=n;i++){a[i]=read();f[i][1]=f[i][0]=0x7fffffff;sum[i]=sum[i-1]+abss(a[i]-a[i-1]);}f[n][0]=f[n][1]=0;a[n+1]=a[n];for(R ll i=n-1;i>=1;i--){f[i][0]=minn(f[i+1][0]+abss(a[i+1]-a[i]),f[i+1][1]+abs(a[i+2]-a[i]));for(R ll j=i+1;j<=n-1;j++)f[i][1]=minn(f[i][1],minn(f[j+1][0]+abss(a[i]-a[j+1]),f[j+1][1]+abss(a[i]-a[j+2]))+sum[j]-sum[i+1]+abss(a[i]-a[j]));f[i][1]=minn(f[i][1],sum[n]-sum[i+1]+abss(a[n]-a[i]));}write(minn(f[1][0],f[1][1]));return 0;
}
p.s. 听说自己手写函数会比调用自带的函数跑得快，建议各位自己手写函数（虽然这题没必要）。