[45]合唱-网易2018秋

1.题目描述

小 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
  

2.题目解析

一个音调要么是小Q的，要么是牛博士的。

选择综合征最佳解决办法：每种情况选择一次，取最优者。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2001; // 多保留1个位置
int v[maxn];
int n;
int solve(int la, int lb) { // la和lb分别表示小Q与博士最后唱的音符位置，
  int now = max(la, lb) + 1; // now表示新的一个音符的位置
  if (now == n + 1) // 没有音符，数组结束
    return 0;
  // 当la和lb为0表示未选择音符
  return min(
      solve(now,lb) + (la ? abs(v[now] - v[la]) : 0),
      solve(la,now) + (lb ? abs(v[now] - v[lb]) : 0));
}
int main() {
  scanf("%d", &n);
  // 第一个元素不使用，下标从1开始使用，便于计算
  for (int i = 1; i <= n; ++i)
    scanf("%d", &v[i]);
  printf("%d\n", solve(0, 0));// 0表示没有选择音符
  return 0;
}

问题

• 为什么使用最后唱的音符位置作为参数？之前的音符计算完成后不再使用，而最后唱的音符可能需要与新的音符运算，所以需要作为参数。
• 难度和在哪里计算？难度和在return语句中(函数返回值栈中)。

下图中，可以看出里面有很多重复计算的情况，使用数组把计算结果缓存可以提高效率。

动态规划本质：枚举+备忘录

3.参考答案

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2001; // 多保留1个位置
int v[maxn];
int n;
int dp[maxn][maxn]; // 备忘录，保存过程计算
int solve(int la, int lb) { // la和lb分别表示小Q与博士最后唱的音符位置，
  int now = max(la, lb) + 1; // now表示新的一个音符的位置
  if (now == n + 1) // 没有音符，数组结束
    return 0;
  if (dp[la][lb] != -1) return dp[la][lb];
    // 当la和lb为0表示未选择音符
  return dp[la][lb] = min(
      solve(now,lb) + (la ? abs(v[now] - v[la]) : 0),
      solve(la,now) + (lb ? abs(v[now] - v[lb]) : 0));
}
int main() {
  scanf("%d", &n);
  // 第一个元素不使用，下标从1开始使用，便于计算
  for (int i = 1; i <= n; ++i)
    scanf("%d", &v[i]);
  memset(dp, -1, sizeof(dp));
  printf("%d\n", solve(0, 0));// 0表示没有选择音符
  return 0;
}

牛客题目