踏む石を選択するのではなく、飛ばす石を選択すると考えると見通しが良くなります。これを念頭に問題を読み替えると、以下の形になります。

• 高々 \(K\) 個の石を飛ばす。
• ただし、連続する石を両方飛ばしてはいけない。
• 飛ばす石のスコアの総和を最小化せよ。

この問題は以下の問題と同等です。

• JOI ²⁰¹⁷⁄₂₀₁₈ 春季トレーニング合宿 Day4 問題1 飴 (Candies)
  • AtCoder上のジャッジ
  • 公式解説

解法だけ抜き出すと、次の貪欲法が成立します。

• \(A\) 中のある要素 \(A_i\) を選択したとする。
• このとき、 \(A_{i-1},A_{i},A_{i+1}\) を削除し、ここに \(A_{i-1}+A_{i+1}-A_i\) を挿入する。
• 上記のルールを守りながら \(A\) のうち最も小さいものを貪欲に選択することを繰り返してよい。

priority_queue と連結リストを適切に利用することで実装でき、全体の時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

using ll=long long;
using pl=pair<ll,ll>;

int main(){
  ll N,K;
  cin >> N >> K;
  K=min(K,(N-1)/2);
  vector<ll> A(N+2);
  ll tot=0;
  for(ll i=1;i<=N;i++){
    cin >> A[i];
    tot+=A[i];
  }
  ll cres=0;
  A[0]=1e18; A[1]=1e18;
  A[N]=1e18; A[N+1]=1e18;
  priority_queue<pl,vector<pl>,greater<pl>> pq;
  vector<ll> lef(N+2),rig(N+2);
  vector<ll> alive(N+2,1);
  for(ll i=0;i<N+2;i++){
    lef[i]=i-1;
    rig[i]=i+1;
    pq.push({A[i],i});
  }
  ll res=cres;
  ll hand=0;
  while(hand<K){
    auto od=pq.top(); pq.pop();
    if(alive[od.second]==0){continue;}
    cres+=od.first;
    res=min(res,cres);
    hand++;
    ll el=lef[od.second];
    ll er=rig[od.second];
    A[od.second]=A[el]+A[er]-A[od.second];
    pq.push({A[od.second],od.second});
    {
      alive[el]=0;
      ll x=lef[el],y=rig[el];
      lef[y]=x; rig[x]=y;
    }
    {
      alive[er]=0;
      ll x=lef[er],y=rig[er];
      lef[y]=x; rig[x]=y;
    }
  }
  cout << tot-res << "\n";
  return 0;
}