某特种部队接到一个任务，需要潜入一个仓库。该部队士兵分为两路，第一路士兵已经在正面牵制住了敌人，第二路士兵正在悄悄地从后方秘密潜入敌人的仓库。
当他们到达仓库时候，发现这个仓库的锁是一把很诡异的电子锁，上面是一排按钮，每个按钮上都有一个数字。10
秒钟后，总部返回了该锁的技术信息。要解开这把锁，首先要从左边的第一个按钮开始向右按动，中间可以跳过某些按钮，按动到最右边的按钮后，反向向左按动。最终，每个按钮都要按且仅按一次。每两个相邻按钮上数字之差的总和的最小值，便是解开这把锁的密码。
作为一支装备精良的特种部队，必须要在最短的时间内完成任务，解开这把锁，潜入仓库。
输入描述
Input Description
第一行是一个n（2 <= n <= 1000）表示共有n 个按钮。
第二行是n 个正整数，代表从左至右各按钮上的数字，数值均不超过2000。
输出描述
Output Description
只有一个数，为这把锁的密码。
样例输入
Sample Input
5
1 2 3 4 5
样例输出
Sample Output
4
2 <= n <= 1000，数值不超过2000（随机）
emm...一脸不可做...
然后仔细看了看...
emm...
根据题目的性质，只可以来回走一次并且还要全部遍历一遍。
再仔细看看...
"按动到最右边的按钮后，反向向左按动".
这意味着，我们从前往后走和从后往前走，都需要经过第n号节点，所以我们可以把操作想象成都从后往前移动， 并且中间不能重复经过同一个点...
emm...分析完，题目渐渐变得可做。
我们设f[i][j]表示两端分别到了i, j这两个位置， 为了方便，我们设i < j.
于是，我们就得到了转移方程：
1. i接着往前走一格,f[i-1][j] = f[i][j] + abs(a[i-1]-a[i]);
2. j调到i-1的位置超过i, f[i-1][i] = f[i][j] + abs(a[i-1]-a[j]);
因为我们已经承诺过状态里的i < j，所以没有别的转移方程。
对了..题目描述不是特别好，两个相邻按钮的数字差的绝对值计入答案。
然后...AC？
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read()
{
int X=,w=; char ch=;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
int n, a[];
int f[][];
signed main()
{
n = read();
for (int i = ; i <= n ; i ++) a[i] = read();
memset(f, 0x3f, sizeof f);
f[n][n] = ;
f[n][n-] = f[n-][n] = abs(a[n]-a[n-]);
for (int i = n - ; i >= ; i --)
{
for (int j = n ; j >= i + ; j--) //i <= j
{
f[i-][j] = min(f[i-][j], f[i][j] + abs(a[i-]-a[i]));
f[i-][i] = min(f[i-][i], f[i][j] + (int)abs(a[j]-a[i-]));
}
}
int ans = 1e9;
for (int i = ; i <= n ; i ++) ans = min(ans, f[][i]);
cout << ans;
return ;
}