F

简单动态规划问题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll f[N];
ll a[N];
int main()
{
    memset(f,0x3f,sizeof f);
    f[1]=0;
    int n,k;
    cin >> n >>k;
    for(int i=1;i<=n;i++)cin >>a[i];
    
    for(int i=1;i<=n;i++)
    {
        for(int j=min(i+k,n);j>i;j--)
        {
            f[j]=min(f[i]+abs(a[i]-a[j]),f[j]);
        }
    }
    cout <<f[n];
}