笔试-合唱

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/fddf64d5757e41ec93f3ef0c0a10b891

题意

小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]（j>i）为两个人最近唱的音调分别为第i个和第j个。
状态转移：
如果i==j-1,也就是换人演唱的时候，DP[i][j]也就是DP[j-1][j]的值应该为DP[k][j-1]+abs(v[k][j]),k为这个人上次演唱的音调位置。
如果i<j-1,也就是最近演唱的人继续演唱当前字符，DP[i][j]的值应该为DP[i][j-1]+abs(v[j]-v[j-1])。
最后结果应该DP[i][n],1<=i<n中的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    vector<int> v(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    vector< vector<int> > dp(n+1,vector<int>(n+1));
 
    for(int i=1;i<=n;i++){
        if(i>2) dp[i-1][i] = dp[i-2][i-1] + abs(v[i-1]-v[i-2]);
    }
 
//    for(int i=0;i<=n;i++){
//        for(int j=0;j<=n;j++){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
 
    for(int j=1;j<=n;j++){
        for(int i=1;i<j-1;i++){
            dp[i][j]=dp[i][j-1]+abs(v[j]-v[j-1]);
            dp[j-1][j]=min(dp[j-1][j],dp[i][j-1]+abs(v[i]-v[j]));
        }
    }
    int ans = INT_MAX;
    for(int i=1;i<n;i++){
        ans=min(ans,dp[i][n]);
    }
    cout<<ans<<endl;
    return 0;
}