[CODEVS6333] （数据加强）特种部队

题目描述 Description

某特种部队接到一个任务，需要潜入一个仓库。该部队士兵分为两路，第一路士兵已经在正面牵制住了敌人，第二路士兵正在悄悄地从后方秘密潜入敌人的仓库。
当他们到达仓库时候，发现这个仓库的锁是一把很诡异的电子锁，上面是一排按钮，每个按钮上都有一个数字。10 秒钟后，总部返回了该锁的技术信息。要解开这把锁，首先要从左边的第一个按钮开始向右按动，中间可以跳过某些按钮，按动到最右边的按钮后，反向向左按动。最终，每个按钮都要按且仅按一次。每两个相邻按钮上数字之差的总和的最小值，便是解开这把锁的密码。
作为一支装备精良的特种部队，必须要在最短的时间内完成任务，解开这把锁，潜入仓库。

输入描述 Input Description

第一行是一个n（2 <= n <= 1000）表示共有n 个按钮。
第二行是n 个正整数，代表从左至右各按钮上的数字，数值均不超过2000。

输出描述 Output Description

只有一个数，为这把锁的密码。

样例输入 Sample Input

5
1 2 3 4 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

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=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
} 
int n, a[1005];
int f[1005][1005];
signed main()
{
    n = read();
    for (int i = 1 ; i <= n ; i ++) a[i] = read();
    memset(f, 0x3f, sizeof f);
    f[n][n] = 0;
    f[n][n-1] = f[n-1][n] = abs(a[n]-a[n-1]);
    for (int i = n - 1 ; i >= 1 ; i --)
    {
        for (int j = n ; j >= i + 1 ; j--) //i <= j
        {
            f[i-1][j] = min(f[i-1][j], f[i][j] + abs(a[i-1]-a[i]));
            f[i-1][i] = min(f[i-1][i], f[i][j] + (int)abs(a[j]-a[i-1]));
        }
    }
    int ans = 1e9;
    for (int i = 2 ; i <= n ; i ++) ans = min(ans, f[1][i]);
    cout << ans;
    return 0;
}