【题目描述】
小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和牛博士演唱最小的难度和是多少。
【示例】
【输入】
5
1 5 6 2 1
【输出】
3
【问题分析】(思路来源于牛客网昵称 “啊打头的名字会排在前面” 用户,在此非常感谢)
子问题的话还是dp[j][i] 表示两个人唱的最后两个音符的位置是i和j。其中(j<i)
研究dp[j][i]的转移方程:
如果j+1==i; 比如dp[3][4]那么,其可以到达它的状态有{dp[0][3],dp[1][3],dp[2][3],还有一种情况是3的前面全是由一个人唱的},计算这些前置状态+本次决策的收益并进行比较。
如果j+1!=i; 说明这个状态只能由dp[j][i-1]达到,比如dp[3][5] 它的前状态一定是dp[3][4]
【代码】
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<memory.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define mem(array) memset((array),0,sizeof((array)))
#define Qsort(array,len,cmp) qsort(array,len,sizeof(array[0]),cmp)
#define inf 0x7fffffff
#define MAXN 10+2000
using namespace std;
int dp[MAXN][MAXN];
int v[MAXN];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",tdout);
int n;
while(cin>>n){
mem(v);
for(int i = 1; i <= n; ++i)
scanf("%d",&v[i]);
mem(dp);
for(int i = 1; i <= n; ++i){
for(int j = 0; j < i; ++j){
if(j+1 == i){
dp[j][i] = dp[0][j];
for(int k = 1; k < j; ++k){
dp[j][i] = min(dp[j][i],dp[k][j] + abs(v[k]-v[i]));
}
}
else{
dp[j][i] = dp[j][i-1] + abs(v[i-1]-v[i]);
}
}
}
int ans = dp[0][n];
for(int i = 1; i < n; ++i)
ans = min(ans,dp[i][n]);
cout<<ans<<endl;
}
return 0;
}
题目来源于 牛客网