首页 > 试题广场 >

合唱

[编程题]合唱

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

输出

算法知识视频讲解

Java

啊打头的名字会排在前面

子问题的话还是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)

Java

buaaqlyj

动态规划题

dp[i][j]（永远有i > j）表示某一个人最近唱的音为第i个，另一个人最近唱的是第j个时最小的难度
由于只由一个人唱完肯定不是最优解。因此先在一个for循环内确定以下两种情况的初值
dp[i][0]：第二个人唱第一个音，第一个人唱后面所有音
dp[i][i-1]：第一个人唱最近的一个音，第二个人唱前面所有音
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])
最后求出所有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)