首页 > 试题广场 >

合唱

[编程题]合唱

热度指数：4632 时间限制：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

输出

算法知识视频讲解

JavaScript

pma934

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)