首页 > 试题广场 >

合唱

[编程题]合唱
  • 热度指数:4629 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
小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

输出

3
n = int(raw_input())
data = map(int, raw_input().split())
dp = [[0]*n for _ in range(n)]
for i in range(2,n):
    dp[i][i-1] = dp[i-1][i-2] + abs(data[i-1]-data[i-2])
for i in range(2, n):
    for j in range(i-1):
         #每当交换唱歌次序,两人最近一次唱的音符一定是相邻的,所以底下分相邻和不相邻讨论:
        dp[i][j] = dp[i-1][j] + abs(data[i]-data[i-1])
        choice = dp[i-1][j] + abs(data[i]-data[j])
        dp[i][i-1] = min(choice, dp[i][i-1])
print min(dp[n-1][:-1])
发表于 2018-03-27 13:53:15 回复(2)

典型的序列型DP,思路可以参考高赞回答@buaaqlyj或者@夭寿啦要没Offer啦
本套8道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int n; cin >> n;
    int *data = new int[n];
    cin >> data[0];
    int *DP = new int[n*n];
    int sum = 0;
    for (int i = 1; i < n; i++) {
        cin >> data[i];
        DP[i*n + i - 1] = sum;
        sum += abs(data[i] - data[i - 1]);
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i - 1; j++) {
            DP[i*n + j] = DP[(i - 1)*n + j] + abs(data[i] - data[i - 1]);
        }
        for (int k = 0; k < i - 1; k++) {
            DP[i*n + i - 1] = min(DP[i*n + i - 1], DP[(i - 1)*n + k] + abs(data[i] - data[k]));
        }
    }
    int result = DP[(n - 1)*n];
    for (int i = 1; i < n - 1; i++) {
        result = min(result, DP[(n - 1)*n + i]);
    }
    cout << result;
    delete[] DP;
    return 0;
}
发表于 2017-10-10 10:41:29 回复(0)
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int v[2010],n,dp[2010][2010];
int d(int,int);
int main() {
    scanf("%d",&n);
    v[0]=-1;
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d\n",d(0,0));
}
int d(int i,int j){
    int k=max(i,j)+1;
    if(k==n+1) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    dp[i][j]=999999999;
    dp[i][j]=min(dp[i][j],d(k,j)+(i?abs(v[k]-v[i]):0));
    dp[i][j]=min(dp[i][j],d(i,k)+(j?abs(v[k]-v[j]):0));
    return dp[i][j];
}//记忆搜索 dp[i][j]表示 小Q和牛博士上一个音调分别为v[i]和v[j]

发表于 2017-09-18 19:53:12 回复(2)
var len = Number(readline())
var list = readline().split(' ').map(x=>Number(x))
if(len<3){
    print(0)
}else{
    var dp = new Array(len).fill(1).map(_=>[0])
    var sum = new Array(len).fill(0)  //考虑前面i-1种音调由一个人唱时
    for(let i=2;i<len;i++){
        sum[i] = sum[i-1]+Math.abs(list[i-1]-list[i-2])
        dp[i][i-1] = sum[i]
        for(let j=0;j<i-1;j++){
            dp[i][j]=dp[i-1][j]+Math.abs(list[i]-list[i-1])
            dp[i][i-1] = Math.min(dp[i][i-1],dp[i-1][j] + Math.abs(list[i]-list[j]))
        }
    }
    print(Math.min(...dp[len-1]))
}

js版本,思路参考 buaaqlyj 的回答

令dp[i][j]表示某一个人最近唱的音为第i个,另一个人最近唱的是第j个时最小的难度

则实现如下规律即可

当j=i-1时:
考虑前面i-1种音调由一个人唱时 
dp[i][j]_1 = sum{list[i]-list[i-1]},i∈[1,len-2] (第一个 到 倒数第二个音调之间的差值总和)
考虑前面i-1种音调由两个人唱时
dp[i][j]_2 = min{ dp[k][j] + |list[i]-list[k]| } 
           = min{ dp[i-1][k] + |list[i]-list[k]| },k∈[0,i-2]
dp[i][j] = min{dp[i][j]_1,dp[i][j]_2}

当j≠i-1时:
dp[i][j] = dp[i-1][j] + |list[i]-list[i-1]|

最后求出min{dp[i][k]},k∈[0,i-1]
编辑于 2019-07-02 01:37:22 回复(0)
// 参考了上面各位大神的思路,得出递推公式:
// dp[i][i-1] = min(dp[i-1][k] + abs(v[i] - v[k])),(0<=k<j)
// dp[i][j] = dp[i-1][j] + abs(v[i] - v[i-1]), (i-1>j)
// 有边界条件,dp[1][0]=0;
// dp[1][0]=>dp[1...n-1][0]
// dp[1][0],dp[2][0]=>dp[2][1]=>dp[2...n-1][1]
// ......
// dp[1...n-2][0...n-2]=>dp[n-1][n-2]
// 类推,可以得到所有[i,j]的值,找出dp[n-1][]中最小值即可。
#include<stdio.h>

#include<stdlib.h>

#define MaxN 2000

int n;

int v[MaxN]={0};

int dq[MaxN][MaxN]={0};

void work(){

    dq[1][0] = 0;

    for (int j=0; j<n-1; j++) {

        for (int i=j+2; i<n; i++) {

            dq[i][j] = dq[i-1][j]+abs(v[i]-v[i-1]);

        }

        if (j+2<n) {

            dq[j+2][j+1]=dq[j+1][0]+abs(v[1]-v[0]);

            for (int k=0; k<j+1; k++) {

                int tmp=dq[j+1][k]+abs(v[j+2]-v[k]);

                dq[j+2][j+1]= dq[j+2][j+1]<=tmp ? dq[j+2][j+1] : tmp;

            }

        }

    }

    int result=dq[n-1][0];

    for (int i=1; i<n-1; i++) {

        result = result<=dq[n-1][i] ? result : dq[n-1][i];

    }

    printf("%d",result);

}

int main(){

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        scanf("%d",&v[i]);

    }

    work();

}


编辑于 2018-04-03 22:19:52 回复(0)
/*参考【buaaqlyj】大佬的,思维很活跃,厉害*/
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ints = new int[n];//用来接收所有的音节数
        for (int i = 0; i < n; i++) {
            ints[i] = scanner.nextInt();
        }
        //若n<3,则返回0
        if (n < 3) {
            System.out.println(0);
        } else {
            //dp[i][j]表示第一个人上一个音符为i,第二个人上一个音节为j,此时的最小难度
            int[][] dp = new int[n][n];
            //acc数组标记所有音符不分组的绝对差值累加和
            int[] acc = new int[n];
            //下列循环中当i=1,j=0时
            //dp[1][0]=dp[0][0]+Math.abs(ints[1]-ints[0])
            //dp[1][0]=0;
            //dp[0][0] = 0 - Math.abs(ints[1] - ints[0]);第二个循环写到j=0,所以此处dp[0][0]无意义
            for (int i = 1; i < n; i++) {
                acc[i] = acc[i - 1] + Math.abs(ints[i] - ints[i - 1]);//求出不分组时绝对差值累加和
                //第一个人只唱了第i个音符,第二个人唱了【0,i-1】的音符,
                //所以第一个人难度为0,第二个人难度为【0,i-1】的累计难度,即acc[i-1]
                dp[i][i - 1] = acc[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时
                    //当j=i-1的情况,用j代表之前公式中的k
                    //不用再写一个for循环去遍历k找最小的难度,优化代码,就是思维有点跳跃
                    dp[i][i - 1] = Math.min(dp[i][i - 1], dp[i - 1][j] + Math.abs(ints[i] - ints[j]));
                }
            }
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < n - 1; ++j) {
                min = Math.min(min, dp[n - 1][j]);
            }
            System.out.println(min);
        }
    }
}
 
发表于 2018-03-25 17:07:18 回复(0)
这道题我有一个很简单的思路。不过这样做只能通过60%的样例。不知道哪里错了,希望高手们能指点迷津。
第一个人唱低音,第二个人唱高音,先把数组排个序,然后选择前一部分作为低音,后一部分作为高音。
分割的标准是两个元素间隔最大的地方。

发表于 2018-03-12 15:34:47 回复(5)

一点点思考的过程,感觉有点乱,记录下来

第一个维度是当前一个人唱第i个位置的音符,第二个维度不好找。第二个维度如果也是音符的话,那么就必须有先后关系。第二个维度是另一个人之前唱到的音符,c[i][j]是此时最小难度和。

c[i][j]可能由哪些状态转移过来呢?
例如某人唱到了第6个音符,另一个人最后一次唱到了第3个音符,此时如果当前的总的难度是最小的,那么有以下结论:
第6个音符、第5、第4个音符都是第一个人唱的。因为第二个人才唱到了第三个音符,他不可能去唱后面的音符。
所以c[6][3] = c[5][3] + 56难度差。
但是c[4][3]是怎么转移来的呢?如果此时第一个人唱到了第4个音符,另一个人唱到了第3个音符,这说明第一个人唱第4个音符中断了第二个人唱的音符。由于不知道上一次第一个人是从哪里跳到第4个音符的,所以我们分别假设是从可能的所有音符跳过来的,如果是从第二个音符跳过来的,那么就是c[3][2]+ 34差。如果是从第一个音符跳过来的,那么就是c[3][1]+14差。如果是从没有跳过来的,那么就是c[3][0]+04差。由于第一个人唱的时候,第二个人上一次唱的总是比第一个人唱的要小,所以我们不需要考虑j>=i的时候。

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <array>

using namespace std;

vector<int> nums;
array<array<int, 2100>, 2100> dp;

// 计算两个音符之间的难度。注意第一个音符的下标在输入数据里面是0,有个差1的关系。如果起始音符是0,说明第一次唱,不增加难度 */
int diffcult(int s, int e)
{
    if(s == 0) return 0;
    // printf("diffcult %d %d to %d %d is %d \n", s,nums[s-1], e,nums[e-1], abs(nums[e-1] - nums[s-1]));
    return abs(nums[e-1] - nums[s-1]);
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        nums.push_back(num);
    }

    ///* 从0开始向后考虑,直到考虑完所有音符,第一个人最差的情况是没有唱,此时j也没有唱,直接continue了 */
    for (int i = 0; i <= n; i++)
    {
        ///* 这里也是从0开始考虑,因为第一个人最差一个都不唱,就是处于0 */
        for (int j = 0; j <= n; j++)
        {
            ///* 不考虑后面的情况。当然也可以直接写到上面的范围限制里面 */
            if (j >= i)
                continue;
            ///* 如果是一般情况下,比如第一个人在唱6音符时,第二个人在唱3音符,显然是从dp[5][3]转移来的 */
            if (j + 1 < i)
            {
                dp[i][j] = dp[i - 1][j] + diffcult(i - 1, i);
            }
            ///* 否则,如果第二个人刚唱完就被第一个人抢唱了,那么第一个人唱的音符就可能是前面跳过来的 */
            if (j + 1 == i)
            {
                ///* k表示i是从第几个跳过来的 */
                int min_cost = -1;
                for (int k = 0; k < j; k++)
                {
                    int cost = dp[j][k] + diffcult(k, j + 1);
                    ///* 只用记录最小跳唱难度 */
                    if(min_cost == -1 || min_cost > cost){
                        min_cost = cost;
                    }
                }
                if(min_cost == -1) min_cost = 0;
                dp[i][j] = min_cost;
            }
            // 调试代码,打开可以看推导过程
            // for(int a=0;a<=n;a++){
            //     for(int b=0;b<=n;b++){
            //         if(a==i && b == j){
            //             printf("\t【%d】", dp[a][b]);
            //         }
            //         else printf("\t%d", dp[a][b]);
            //     }
            //     // printf("\n");
            // }
            // printf("\n");
        }
    }
    int min_cost = -1;
    for(int j=0;j<n;j++){
        if(min_cost == -1 || min_cost > dp[n][j]){
            min_cost = dp[n][j];
        }
    }
    printf("%d", min_cost);
}

编辑于 2018-01-22 21:48:26 回复(0)

动态规划题

  1. dp[i][j](永远有i > j)表示某一个人最近唱的音为第i个,另一个人最近唱的是第j个时最小的难度
  2. 由于只由一个人唱完肯定不是最优解。因此先在一个for循环内确定以下两种情况的初值
    dp[i][0]:第二个人唱第一个音,第一个人唱后面所有音
    dp[i][i-1]:第一个人唱最近的一个音,第二个人唱前面所有音
  3. dp[i][j]转移方程
    每当交换唱歌次序,两人最近一次唱的音符一定是相邻的,所以底下分相邻和不相邻讨论:
    (1). 当j == i - 1,即交换唱歌次序,dp[i][i-1]时,表明第一个人上一个音可能在第k个音(0 <= k < i-1),由唱了最近的第i个,第二个人仍然留在第i-1个音。
    dp[i][i-1] = 对所有k求min(dp[i-1][k] + abs(arr[i] - arr[k]) ) 其中(0 <= k < i-1)
    (2). 当j < i - 1,即不交换唱歌次序时,只可能由唱到i-1音符的人续唱
    dp[i][j] = dp[i-1][j] + abs(arr[i] - arr[i-1])

  4. 最后求出所有dp[len-1][]里的最小值即为全局最优解

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int len = in.nextInt();
            int[] arr = new int[len];
            for (int i = 0; i < len; ++i) {
                arr[i] = in.nextInt();
            }
            if (len < 3) {
                System.out.println("0");
            } else {
                int[][] dp = new int[len][len];
                int[] acc = new int[len];
                dp[0][0] = 0 - Math.abs(arr[1] - arr[0]);
                for (int i = 1; i < len; ++i) {
                    acc[i] = acc[i - 1] + Math.abs(arr[i] - arr[i - 1]);
                    dp[i][i - 1] = acc[i - 1];
                    for (int j = 0; j < i - 1; ++j) {
                        dp[i][j] = dp[i - 1][j] + acc[i] - acc[i - 1];
                        dp[i][i - 1] = Math.min(dp[i][i - 1], dp[i - 1][j] + Math.abs(arr[i] - arr[j]));
                    }
                }
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < len - 1; ++j) {
                    min = Math.min(min, dp[len - 1][j]);
                }
                System.out.println(min);
            }
        }
    }
}
编辑于 2017-09-12 21:03:31 回复(25)
两种方法
正推的话,容易想到一个人继续演唱或换人演唱的时候发生状态转移:
  • 可先设 dp[i][j] 表示当前小Q唱到第 i 个音调,牛博士唱到第 j 个音调的难度和;
  • 不妨设当前 i > j :
    • 若 i - 1 == j 则发生换人,由于不知道上一次 i 唱到哪里,状态由 min{ dp[k][j] + abs(v[i] - v[k]) }, k < j 转移来;
    • 若 i - 1 > j 则表示当前是从 i - 1 唱到 i 的,没有换人,状态由 dp[i-1][j] + abs(v[i] - v[i-1]) 累加;
  • 不妨设 dp[i][j] 表示当前演唱到第 i 个,上一个人演唱到第 j 个,则状态转移方程为
    dp[i][j] = dp[i-1][j] + abs(v[i] - v[i-1]), j < i - 1
    dp[i][i -1] = min{ dp[i-1][k] + abs(v[i] - v[k]) }, k < i - 1
  • 初始情况是若当前有 i 个音调,可以让一个人只唱第一个或最后一个音调,剩下的音调都由另一个人唱:
    dp[i][0] = dp[i-1][0] + abs(v[i] - v[i-1]), i ≥ 2
    dp[i][i-1] = dp[i-1][i-2] + abs(v[i-1] - v[i-2]), i ≥ 2

反推:
  • 设 dp[i][j] 表示从当前小Q唱到第 i + 1 个音调,牛博士唱到第 j + 1 个音调开始,直到所有音调演唱完的难度和;边界情况 i = 0 或 j = 0 表示一个人还没开始唱;
  • 容易知道下一个音调 next = max{ i, j } ,若让小Q唱下一个音调,会得到 abs(v[next] - v[i]) 的贡献;若让牛博士唱会得到 abs(v[next] - v[j]) 的贡献;
  • 状态转移方程
    dp[i][j] = min{ dp[next][j] + abs(v[next] - v[i]), dp[i][next] + abs(v[next] - v[j]) }, i ≠ j < n

正推代码:
#include <stdio.h>
#include <stdlib.h>

typedef long long llong;

inline void getMin(llong& n, llong x) {
    n > x && (n = x);
}

#define MAXN 2020

int n;
int v[MAXN], cost[MAXN];

void read() {
    scanf("%d%d", &n, v);
    for (int i = 1; i < n; ++i) {
        scanf("%d", v + i);
        cost[i] = abs(v[i] - v[i - 1]);
    }
}

llong dp[MAXN][MAXN];

void work() {
    llong res = (1ll << 63) - 1;
    for (int i = 2; i < n; ++i) {
    //    dp[i][0] = dp[i - 1][0] + cost[i];
        dp[i][i - 1] = dp[i - 1][i - 2] + cost[i - 1];
    }
    for (int i = 2; i < n; ++i) {
        for (int j = 0; j < i - 1; ++j) {
            dp[i][j] = dp[i - 1][j] + cost[i];
            getMin(dp[i][i - 1], dp[i - 1][j] + abs(v[i] - v[j]));
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        getMin(res, dp[n - 1][i]);
    }
    printf("%lld\n", res);
}

int main() {
    read();
    work();
    return 0;
}

反推要做一些改动:
using std::max;
using std::min;

int n, v[MAXN];

void read() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", v + i);
    }
}

int cost(int a, int b) {
    return a && b ? abs(v[a] - v[b]) : 0;
}
反推的记忆化递推搜索:
llong solve(int i, int j) {
    int next = max(i, j) + 1;
    if (next == n + 1) {
        return 0;
    }
    if (!~dp[i][j]) {
        dp[i][j] = min(solve(next, j) + cost(next, i), solve(i, next) + cost(next, j));
    }
    return dp[i][j];
}

void work() {
    memset(dp, 0xff, sizeof(dp));
    llong res = solve(0, 0);
    printf("%lld\n", res);
}
或者用循环,更简单:
void work() {
    for (int i = n - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            int next = max(i, j) + 1;
            dp[i][j] = min(dp[next][j] + cost(next, i), dp[i][next] + cost(next, j));
        }
    }
    printf("%lld\n", dp[0][0]);
}

编辑于 2017-10-11 22:20:04 回复(11)
子问题的话还是dp[i][j] 表示两个人唱的最后两个音符的位置是i和j。其中(j>i)
研究dp[i][j]的转移方程:
如果i+1==j; 比如dp[3][4]那么,其可以到达它的状态有{dp[0][3],dp[1][3],dp[2][3],还有一种情况是3的前面全是由一个人唱的},计算这些前置状态+本次决策的收益并进行比较。
如果i+1!=j; 说明这个状态只能由dp[i][j-1]达到,比如dp[3][5] 它的前状态一定是dp[3][4]

import java.util.Scanner;
import java.lang.Math;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] data = new int[n];
        for (int i=0;i<n;i++){
            data[i]=sc.nextInt();
        }
         
        int[][] dp = new int[n][n];
        for (int i=0;i<n;i++){
            for (int j=i+1;j<n;j++){
                if (j==i+1){
                    if (i==0){
                        dp[i][j] = 0;
                    }else{
                        int result = Integer.MAX_VALUE;
                        for (int z=0;z<i;z++){
                            int current_result = dp[z][i] + Math.abs(data[j]-data[z]);
                            result = current_result<result?current_result:result;
                        }
                        int result_all_A = 0;
                        for (int z=1;z<j;z++){
                            result_all_A = result_all_A + Math.abs(data[z]-data[z-1]);
                        }
                        dp[i][j] = (result_all_A<result)?result_all_A:result;
                    }
                }else{
                    dp[i][j] = dp[i][j-1]+Math.abs(data[j]-data[j-1]);
                }
            }
        }
        int final_result = Integer.MAX_VALUE;
        for (int i=0;i<n-1;i++){
            final_result = dp[i][n-1]<final_result?dp[i][n-1]:final_result;
        }
        System.out.println(final_result);
    }
}



编辑于 2017-09-13 14:33:52 回复(2)
动态规划,python

n = int(input().strip('\n'))
voice = [int(x) for x in input().strip('\n').split(' ')]
dp = [[0]*n for _ in range(n)]
s = abs(voice[1] - voice[0])
for i in range(2, n):
    dp[i][0] = dp[i-1][0] + abs(voice[i] - voice[i-1])
    dp[i][i-1] = s
    s += abs(voice[i] - voice[i-1])
    
for i in range(2, n):
    for j in range(i):
        if j < i-1:
            dp[i][j] = dp[i-1][j] + abs(voice[i] - voice[i-1])
        else:
            dp[i][j] = min([dp[i][i-1]] + [dp[i-1][k] + abs(voice[i] - voice[k]) for k in range(i-1)])
print(min(dp[-1][:-1]))


发表于 2019-09-15 17:16:55 回复(0)
#include<vector>
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;



int main()
{
    int n;
    scanf("%d",&n);
    vector<long> array;  //音调序列
    int i=0;
    for(i=0;i<n;i++)
    {
        long v;
        scanf("%ld",&v);
        array.push_back(v);
    }
    
    //dp矩阵
    vector<vector<long> > dp(n, vector<long> (n,0) );
    
    dp[1][0]=0;
    vector<long> special_;  //存放紧邻对角线的串,存放的是某个人最近唱第k个,前面其它的的都由另一个人唱的特殊情况
    special_.push_back(0);
    special_.push_back(0);
    for(int k=2;k<n;k++)
    {
        int c = k-1;
        long special = 0;
        for(int h=0;h<=c-1;h++)
        {
            special += abs( array[h+1]-array[h] );
        }
        special_.push_back(special);
    }
    
    //开始填写dp的其余元素 
    //最前面一列
    for(i=2;i<n;i++)
    { 
        dp[i][0]= 0; //dp[2][0] dp[3][0] dp[4][0]...
        for(int u=1;u<i;u++)
        {
            dp[i][0] += abs(array[u+1]-array[u]);
        }
    }
    
    //其余
    for(int j=2;j<n;j++)
    {
        for(int e=1;e<=j-1;e++)
        {
            if(e==j-1) //填紧邻对角线的串
            {
                long min = special_[j];  //特殊情况
                for(int r=0;r<j-1;r++) // j-1=1
                {
                    if( dp[j-1][r] + abs(array[j]-array[r]) < min )
                        min = dp[j-1][r] + abs(array[j]-array[r]);
                }
                dp[j][e]=min;
            }
            else
            {
                dp[j][e]=dp[j-1][e]+ abs(array[j]-array[j-1]);
            }
        }
    }

    long result = dp[n-1][0];
    for(int w=0;w<n-1;w++)
    {
        if(dp[n-1][w]<result)
            result = dp[n-1][w];
    }
    cout<<result<<endl;
}
动态规划,按照大神的思路码的,我感觉真要出这种题的话,把思路想出来时间就差不多了OTZ
发表于 2019-08-11 22:28:30 回复(0)

给像我这样的菜鸟,做一个动态规划的傻瓜式讲解.用的还是上面大佬们的思想

假设有n个数字,从1开始每次加一个,去掉绝对最差的.

比如 (3,4):5 (4,3):7 (3,4):8 仅保留(3,4):5

设置 m[i=5][j=5] 代表在放入第i个数时,一人最后一唱为i,另一人为j (j<i)

思想: 一生二,二生四(去除相同,取最小),三生六.....

举例

输入:

5

1 5 6 1 2

  1. (1,0):0

  2. (2,0):|1-5|=4 (2,1):0

----2的俩项由1生成

  1. (3:0):5 (3:2):4 (3,1):1 (3,2):5

----3的四项由2的俩项生成,其中重复的(2,3)取最小

......直到去取完

可以发现,比如

                   (4,0)生成(5,0) (5,4)
                   (4,1)生成(5,1) (5,4)
                   (4,2)生成(5,2) (5,4)
                   (4,3)生成(5,3) (5,4)

即可以直接在m[i+1]中直接加入m[i]中的生成的前 i 项,最后一位为相同项的最小值.

```
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n,tmp; cin >> n;
    vector<int> x(n);
    vector<vector<int>> m(n);
    vector<int> arr;
    m[0].push_back(0);
    cin >> x[0];
    for (int i = 1; i < n ; i++)
    {
        cin >> x[i];
        m[i].push_back(m[i - 1][0] + abs(x[i] - x[i - 1]));
        arr.push_back(m[i - 1][0]);
        for (int j = 1; j < i; j++)
        {
            m[i].push_back(m[i-1][j] + abs(x[i-1] - x[i]));
            arr.push_back(m[i-1][j] + abs(x[j-1] - x[i]));
        }
        tmp = *min_element(arr.begin(), arr.end());
        m[i].push_back(tmp);
        arr.clear();
    }
    /*查看m表
    for (auto p : m)
    {
        for (auto k : p)
            cout << k << " ";
        cout << endl;
    }
    */
    int ans = *min_element(m[n - 1].begin(), m[n - 1].end());
    cout << ans;
    system("pause");
}

































编辑于 2019-08-06 20:43:11 回复(0)
py3版本:
n=int(input())
ns=[int(i) for i in input().split(' ')]
dp=[[0]*n  for i in range(n)]
#特殊位置初始化
for i in range(2,n):
    dp[i][0]=dp[i-1][0]+abs(ns[i]-ns[i-1])
    dp[i][i-1]=dp[i-1][i-2]+abs(ns[i-1]-ns[i-2])
#逐步动态规划
for i in range(2,n):
    for j in range(i-1):
        dp[i][j]=dp[i-1][j]+abs(ns[i]-ns[i-1])
        dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+abs(ns[i]-ns[j]))
print(min(dp[-1][:n-1]))

发表于 2018-09-03 22:10:44 回复(2)
/*
小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,这一个是最小难度和的方案了。
*/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
int dp[2001][2001];

//dp[i][i-1]表示最近的一个音一个人唱前面的有另一个人唱
int main()
{
    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 2; i < n; i++)
    {
        //初始情况dp[i][0];
        dp[i][0] = dp[i - 1][0] + abs(a[i] - a[i - 1]);
        //dp[i][i-1]表示最近的一个音一个人唱前面的有另一个人唱
        dp[i][i - 1] = dp[i - 1][i - 2] + abs(a[i - 1] - a[i - 2]);
        
    }


    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (j+1<i)
            {
                dp[i][j] = dp[i - 1][j] + abs(a[i] - a[i - 1]);
            }
            else if (j = i - 1)
            {
                for (int k = 0; k < j; k++)
                {
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(a[i] - a[k]));
                }
            }
            
        }
        
    }
    int min1 = INT_MAX;
    //结束时最小和
    for (int i = 0; i < n-1; i++)
    {
        min1 = min(min1, dp[n - 1][i]);
    }
    cout << min1;
}
发表于 2018-05-08 10:39:09 回复(0)
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
#include <vector>
#include "algorithm"
#include <set>
#include <stdlib.h>
using std::cin;
using std::cout;
using  std::endl;
using  std::string;
using  std::pair;
using std::vector;

/*
 * ddepth[i][j]=depth[j][i] 所以这个矩阵是对称矩阵 所以我们在处理的时候只需要处理下班部分就行了 所以可以提出简化条件 j<i
 * -------> depth[i][j]=min ( depth[x][j] + abs(value_i-x) )
 */

int min(int &a,int &b)
{
    return  a<b?a:b;
}

int ab(int a)
{
    return a>0?a:-a;
}

int main()
{
    int n=0;
    cin>>n;
    vector<int> list(n+1,0);  //不要list第一个数
    vector<vector<int>> depth(n+1,vector<int>(n+1,0));
    for (int i = 1; i <=n; ++i)
    {
        cin>>list[i];
    }
    depth[1][0]=depth[0][1]=list[0];

    //正式进入dp递归的算法
    for(int i=2;i<n+1;i++)   //最外层的循环每一层都是一个边界
    {
        for (int j = 0; j <i ; ++j)
        {
            int sum=-1;
            // 上一步是交给了B
            if(j==i-1)
            {

                for (int k = 0; k < j; ++k)
                {
                    int result=0;

                    if(k!=0)
                        result=depth[k][j]+ab(list[i]-list[k]);
                    else
                        result=depth[k][j];  //k=0 A增加点 不增加难度

                    if(sum==-1) sum=result;
                    else sum=min(sum,result);
                }
            } else{
                //上一步还是自己走的
                sum=depth[i-1][j]+ab(list[i]-list[i-1]);
            }
            depth[i][j]=sum;
            depth[j][i]=sum;
        }
    }
    int final=depth[n][0];
    for (int l = 1; l <n ; ++l)
    {
        final=min(depth[n][l],final);
    }
    cout<<final<<endl;

}

发表于 2018-04-18 14:07:15 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];//保存音调
        int[] cost = new int[n];//保存音调差的总和,cost[1] = Math.abs(arr[1] - arr[0]) + cost[0]
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if(i >= 1)cost[i] = Math.abs(arr[i] - arr[i-1]) + cost[i-1];
        }
        if(n < 3)System.out.println(0);
        else {
            //定义二维数组dp[n][n],其中dp[i][j]表示其中一个人最后唱第i个,另一个人最后唱第j个的时候的最小代价。(i>j)
            int[][] dp = new int[n][n];
            dp[1][0] = 0;//一个人最后唱的是第1个,一个人最后唱的是第0个
            for(int i = 2; i < n; i++) {
                dp[i][i-1] = cost[i-1];//一个人唱第i个,前面0到i-1让另一个人唱,没有交叉的情况,不能保证代价最小。
                //下面的循环为了求出dp[i][0]....dp[i][i-1],有交叉的情况。
                for(int k = 0; k < i-1; k++) {
                    //假设第一种情况:A要唱第i个,B最后唱的在第k个,k从0到i-2,说明第i-1个肯定也是A唱的
                    dp[i][k] = dp[i-1][k] + cost[i] - cost[i-1];
                    //假设第二种情况:A要唱第i个,B最后唱的是第i-1个,那么A上一次唱的肯定是在第0到i-2个之间
                    dp[i][i-1] = Math.min(dp[i][i-1], dp[i-1][k] + Math.abs(arr[i] - arr[k]));
                }
            }
            int min = Integer.MAX_VALUE;
            //因为dp[i][j]中i>j,所以循环到n-2就停止,要不然最小值输出为0
            for(int i = 0; i < n - 1; i++) {
                min = Math.min(dp[n-1][i], min);
            }
            System.out.println(min);
        }
    }
}
发表于 2018-04-11 16:15:56 回复(0)
/*
 * 参考大神的解题思路:https://www.nowcoder.com/questionTerminal/fddf64d5757e41ec93f3ef0c0a10b891
 * 使用动态规划,dp[i][j]表示最近一次第一个人唱的是i,第二个人唱的是j
 * 不妨设置i>j:
 * 当j = i-1,说明发生了交换的情况,dp[i][j] = dp[i-1][k]+min(abs(nums[i]-nums[k])), 0<=k<i-1;
 * 当j<i-1,说明唱i字符的时候没有发生交换的情况,dp[i][j] = dp[i-1][j]+abs(nums[i]-nums[i-1])
 * */
public class Chorus {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = scanner.nextInt();
            }
            int[] acc = new int[n];
            int[][] dp = new int[n][n];
            for (int i = 1; i < n; i++) {
                acc[i] = acc[i - 1] + Math.abs(nums[i] - nums[i - 1]);
//                初始化dp[i][i-1]
                dp[i][i - 1] = acc[i - 1];
                for (int j = 0; j < i - 1; j++) {
//                    第一种情况
                    dp[i][j] = dp[i - 1][j] + acc[i] - acc[i - 1];
//                    第二种情况
                    dp[i][i - 1] = Math.min(dp[i][i - 1], dp[i - 1][j] + Math.abs(nums[i] - nums[j]));
                }
            }
//            统计最小值
            int min = dp[n - 1][0];
            for (int i = 1; i < n - 1; i++) {
                min = Math.min(min, dp[n - 1][i]);
            }
            System.out.println(min);
        }
    }
}
发表于 2018-03-27 11:07:37 回复(0)
数组的减一真是让我晕的够呛!花了两个小时才找明白错误……
发表于 2018-03-24 14:24:47 回复(0)