【DP】mobiusp正在创作乐曲
输入样例1：
5 2
1 7 7 1 3输出样例1：
2
输入样例2：
10 3
2 5 6 4 4 5 7 3 5 6输出样例2：
1
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N=2e5+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 l=max(1,j-k);int r=min(j+k,7);int minv=1e9;//第i个音符的音高可以由第i-1个音符的[l,r]区间里的音高转移过来；//在区间[l,r]中找第i-1个音符修改次数最小；for(int k=l;k<=r;k++){minv=min(minv,f[i-1][k]);}//是否修改；if(a[i]==j) f[i][j]=minv;else f[i][j]=minv+1;}}int minv=1e9;for(int i=1;i<=7;i++){minv=min(minv,f[n][i]);}cout<<minv<<endl;return 0;
}