首页 > 试题广场 >

合唱

[编程题]合唱

热度指数：506 时间限制：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[0][0]=0

dp[1][0]=0

dp[2][0]=dp[1][0]+v[2]-v[1];

dp[2][1]=dp[2][0];


dp[3][0]=dp[2][0]+v[3]-v[2];
dp[3][1]=dp[2][1]+v[3]-v[2];
//dp[3][2]取下列最小值
dp[3][2]=dp[0][2];
dp[3][2]=dp[1][2]+v[3]-v[1];

//0<=j<=i-2
dp[4][0]=dp[3][0]+v[4]-v[3];
dp[4][1]=dp[3][1]+v[4]-v[3];
dp[4][2]=dp[3][2]+v[4]-v[3];

//j==i-1
//dp[4][3]取下列最小值
dp[4][3]=dp[0][3];
dp[4][3]=dp[1][3]+v[4]-v[1];
dp[4][3]=dp[2][3]+v[4]-v[2];

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n+1];
        for(int i=1; i<=n; i++)
            v[i] = sc.nextInt();
        int[][] dp=new int[n+1][n+1];//小Q唱到i，博士唱到j的最小难度和，反过来也一样，故矩阵对称
        
        /*
        dp[2][0]=dp[1][0]+v[2]-v[1];
        
        dp[2][1]=dp[2][0];
        
        
        dp[3][0]=dp[2][0]+v[3]-v[2];       
        dp[3][1]=dp[2][1]+v[3]-v[2]; 
        
        dp[3][2]=dp[0][2];
        dp[3][2]=dp[1][2]+v[3]-v[1];
        
        
        dp[4][0]=dp[3][0]+v[4]-v[3];
        dp[4][1]=dp[3][1]+v[4]-v[3];
        dp[4][2]=dp[3][2]+v[4]-v[3];
        
        dp[4][3]=dp[0][3];        
        dp[4][3]=dp[1][3]+v[4]-v[1];
        dp[4][3]=dp[2][3]+v[4]-v[2];
        */
        
        dp[0][0]=0;
        dp[1][0]=0;
        for(int i=2;i<=n;i++)
        {
        	int min=dp[i-1][0];
        	for(int j=0;j<=i-2;j++)
        	{
        		dp[i][j]=dp[i-1][j]+Math.abs(v[i]-v[i-1]);
        		if(j==0)
        			continue;
        		int value=dp[i-1][j]+Math.abs(v[i]-v[j]);
        		min=min<value?min:value;
        	}
        	dp[i][i-1]=min;
        }
        
        int min=Integer.MAX_VALUE;
        for(int j=0;j<n;j++)
        {
        	int value=dp[n][j];
            min=min<value?min:value;
        }
        System.out.println(min);
    }
}

发表于 2019-09-05 23:30:17 回复(0)