贵阳网站建开发,wordpress qnap nas外网,学校html网站模板,网络设计包括题目描述
mobiusp 创作了一首 n 个音符的乐曲#xff0c;其中第 iii 个音符的音高为 ai #xff0c;但是 mobiusp 对以前的创作风格和黑历史很不满意#xff0c;他希望所有音符的音高 ai 都是 1∼7 的正整数#xff0c;且相邻的音高差不超过 k 。 现在他要修改若干个音符…题目描述
mobiusp 创作了一首 n 个音符的乐曲其中第 iii 个音符的音高为 ai 但是 mobiusp 对以前的创作风格和黑历史很不满意他希望所有音符的音高 ai 都是 1∼7 的正整数且相邻的音高差不超过 k 。 现在他要修改若干个音符的音高使得最终乐曲能让他满意。形式化地说即使得对于任意 i∈[1,n]i有 1≤ai≤7 且对于任意 i∈[1,n−1]i 均有 ∣ai−a(i1)∣≤k。 请你求出他至少需要修改几个音符才能满足这个要求。
输入描述:
第一行两个整数 n,k (1≤n≤105,0≤k≤6)意义见题目描述。第二行 n 个正整数其中第 i 个正整数 ai (1≤ai≤7)表示第 i 个音符的音高。
输出描述:
一行一个整数表示至少需要修改几个音符。
示例1
输入 5 2 1 7 7 1 3 输出 2 说明
将两个 7 更改为 1 最小更改数为 2 可以证明没有更小的满足条件的更改数。输入 10 3
2 5 6 4 4 5 7 3 5 6 输出 1 #includeiostream
#includealgorithm
using namespace std;
const int N1e510;
int a[N];
int f[N][10];//第i个音符中音高为j的最小修改次数
int main()
{int n,k;cinnk;for(int i1;in;i) cina[i];for(int i1;in;i){//第i个音符中可能出现的音高for(int j1;j7;j){int mn1e610;int min1max(j-k,1);//最小范围int max1min(jk,7);//最大范围for(int rmin1;rmax1;r){mnmin(mn,f[i-1][r]);//选最小}//看是否需要修改if(ja[i]) f[i][j]mn;else f[i][j]mn1;}}int mn1e610;//找出第n个音符中音高为j 的最小修改次数for(int i1;i7;i){mnmin(f[n][i],mn);}coutmnendl;return 0;
}
