沈阳网站建设服务平台搜索引擎网络推广方法

题目描述

mobiusp 创作了一首 n 个音符的乐曲，其中第 iii 个音符的音高为 ai​ ，但是 mobiusp 对以前的创作风格和黑历史很不满意，他希望所有音符的音高 ai 都是 1∼7 的正整数，且相邻的音高差不超过 k 。

现在他要修改若干个音符的音高，使得最终乐曲能让他满意。形式化地说，即使得对于任意 i∈[1,n]i，有 1≤ai≤7 ，且对于任意 i∈[1,n−1]i 均有 ∣ai−a(i+1)∣≤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

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int f[N][10];//第i个音符中，音高为j的最小修改次数
int main()
{int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){//第i个音符中可能出现的音高for(int j=1;j<=7;j++){int mn=1e6+10;int min1=max(j-k,1);//最小范围int max1=min(j+k,7);//最大范围for(int r=min1;r<=max1;r++){mn=min(mn,f[i-1][r]);//选最小}//看是否需要修改if(j==a[i]) f[i][j]=mn;else f[i][j]=mn+1;}}int mn=1e6+10;//找出第n个音符中，音高为j 的最小修改次数for(int i=1;i<=7;i++){mn=min(f[n][i],mn);}cout<<mn<<endl;return 0;
}