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;
}