网易2018秋招笔试题——合唱

题目：

小Q和牛博士合唱一首歌曲,这首歌曲由n个音调组成,每个音调由一个正整数表示。
对于每个音调要么由小Q演唱要么由牛博士演唱,对于一系列音调演唱的难度等于所有相邻音调变化幅度之和, 例如一个音调序列是8, 8, 13, 12, 那么它的难度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示绝对值)。
现在要对把这n个音调分配给小Q或牛博士,让他们演唱的难度之和最小,请你算算最小的难度和是多少。
如样例所示: 小Q选择演唱{5, 6}难度为1, 牛博士选择演唱{1, 2, 1}难度为2,难度之和为3,这一个是最小难度和的方案了。

输入描述

输入包括两行,第一行一个正整数n(1 ≤ n ≤ 2000) 第二行n个整数v[i](1 ≤ v[i] ≤ 10^6), 表示每个音调。

输出描述

输出一个整数,表示小Q和牛博士演唱最小的难度和是多少。

输入例子1

5
1 5 6 2 1

输出例子1

3

分析：

动态规划问题。考虑到了动态规划，但是在状态建立上蒙圈了。好好屡清了一下思路，建立相关的状态和状态转移方程才是最重要的。其实很多笔试题最重要的是思路而不是急着写代码。

• 首先，建立二维数组dp[i][j]，代表第一个人最近唱的音为第i个，第二个人最近唱的音是第j个。
  并且i>j，这样设置的关键在于：不用固定死哪个人在前，哪个人在后，最后一个音唱的人必然在前，另一个人在后。
• 设定初始状态。dp[i][0]表示第二个人唱第一个音，剩下i-1个音都是第一个人唱。
  dp[i][i-1]表示第二个人唱前i-1个音，第一个人唱第i个音。
  注意：1）不用纠结第一个人还是第二个人，因为我们只是数值上的比较，两个人谁先谁后都无所谓。这里只是方便建模。
  2）dp[i][0]和dp[i][i-1]都是一个人唱i-1个音，一个人唱1个音，只是初始值，不要在后面觉得他们是对应数组的值，还是会变的。
• 状态转移方程：
  若交换唱歌次序，两个人最近唱的音符必定为一个是k，一个是k+1，两者一定相邻。
  那么我们就唱歌交不交换次序为突破口建立状态转移方程。
  1）j==i-1时，说明第二个人唱第i-1个音，那么在dp[i][j]中，第i个音是第一个人唱的，因此交换了唱歌的人。同时，第一个人在唱第i个音前为第k个音(0<=k<i-1)。
  所以状态转移方程为：
  dp[i][i-1]=min(dp[i-1][k]+abs(acc[i]-acc[k])
  acc为一个数组，是单个人唱歌时难度之和。
  2）j<i-1时，第二个人没唱到第i-1个音，因此后面直到第i个音都是一个人唱，所以状态转移方程为：
  dp[i][j]=dp[i-1][j]+abs(acc[i]-acc[i-1])。
• 最后求出dp[n-1][]里的最小值即为全局最优解。n-1即是n个音，因为我们是从0开始的。

代码实现

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int dp[2001][2001] = {0};
int main()
{
    int n;
    int v[2001] = {0};//每个音上的数
    int acc[2001] = {0};
    //acc[0]就是第一个数， acc[1]就是前两个数之差的绝对值。
    //acc[2]就是第二个数和第三个数之差的绝对值和acc[1]的和，以此类推。
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> v[i];
    if(n<3)
        cout << "0" << endl;//两个音，一人唱一个，必然为0
    else
    {
        for(int i=1;i<n;i++)
        {
            acc[i] = acc[i-1] + abs(v[i]-v[i-1]);
            dp[i][i-1] = acc[i-1];//初始情况下的dp[i][i-1]，前i-1个音都是第二个人唱。
            for(int j=0;j<i-1;j++)
            {
                dp[i][j] = dp[i-1][j]+acc[i]-acc[i-1];
                //j!=i-1，因此第i个音还是第一个人唱。acc[i]-acc[i-1]也可以写成abs(v[i]-v[i-1])。
                //并且为下一行求最小值提供数据。
                dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + abs(v[i] - v[j]));
                //j==i-1，此时i-1个音是另一个人唱的，交换两人在数组中的位置。
                //遍历另一个人从j=0到i-2哪种情况下dp[i-1][j]+abs(v[i]-v[j])最小。
            }
        }
        int min1 = 2147483647;//最大的int值，保证最小值能够刷新该数。
        for(int j=0;j<n-1;j++)
            min1 = min(min1,dp[n-1][j]);
        cout << min1 << endl;
    }
    return 0;
}