概要

\(N\) 日のうち、「働いた日の直後 \(D\) 日は働けない」という間隔制約のもとで最大 \(K\) 日だけ働き、得られる給料の合計を最大化する問題です。日数と使用回数の 2 軸を持つ動的計画法（DP）で解けます。

考察

素朴なアプローチ

まず思いつくのは「働く日の集合を全部試す」方法ですが、部分集合は \(2^N\) 通りあり、\(N \le 5000\) ではまったく間に合いません。

次に「給料が大きい日から貪欲に選ぶ」方法を考えたくなります。しかしこれは誤りです。例えば \(N=3, K=2, D=1\)、\(A = (5, 6, 5)\) のとき、 - 貪欲に \(A_2 = 6\) を先に選ぶと、\(1\) 日目は「\(2\) 日目に働くなら \(1\) 日目は…」ではなく、\(2\) 日目に働くと \(3\) 日目が禁止、\(1\) 日目に働くと \(2\) 日目が禁止なので、\(6\) を選ぶともう何も追加できず合計 \(6\)。 - 一方 \(1\) 日目と \(3\) 日目を選べば \(5 + 5 = 10\) で、こちらが最適です。

このように「大きい方を取る」判断が後の選択肢を潰してしまうため、貪欲法は成立しません。

重要な気づき

制約が「\(i\) 日目に働いたら次に働けるのは \(i + D + 1\) 日目以降」という直前に働いた日だけに依存する形になっている点が鍵です。つまり、

• 何日目まで見たか
• これまで何日働いたか

の 2 つを状態として持てば、それ以前の詳細な選び方は結果に影響しません（同じ状態なら給料が大きい方だけ残せばよい）。これは典型的な DP の形です。

アルゴリズム

\(dp[j][i]\) を「最初の \(i\) 日だけを考え、働いた日数が \(j\) 日以下のときの給料合計の最大値」と定義します（「ちょうど \(j\) 日」ではなく「\(j\) 日以下」とするのがポイントで、こうすると答えが \(dp[K][N]\) 一つで済みます）。

遷移は \(i\) 日目に働くかどうかで場合分けします。

1. \(i\) 日目に働かない：\(dp[j][i-1]\) がそのまま使えます。
2. \(i\) 日目に働く：直前に働いた日は \(i - D - 1\) 日目以下でなければなりません。よって、 $\(dp[j-1][\max(0,\; i-D-1)] + A_i\)$

まとめると $\(dp[j][i] = \max\bigl(dp[j][i-1],\; dp[j-1][\max(0,\,i-D-1)] + A_i\bigr)\)$

初期条件は \(dp[0][i] = 0\)（\(0\) 日も働かないので \(0\) 円）および \(dp[j][0] = 0\) です。

答えは \(dp[K][N]\) です。

具体例（\(N=3, K=2, D=1\), \(A=(5,6,5)\)）で追うと、 - \(dp[1][1]=5,\ dp[1][2]=6,\ dp[1][3]=6\) - \(dp[2][1]=5\)、\(dp[2][2]=\max(dp[2][1], dp[1][0]+6)=6\)、\(dp[2][3]=\max(dp[2][2], dp[1][1]+5)=\max(6, 10)=10\)

となり、正しく \(10\) が得られます。

計算量

• 時間計算量: \(O(NK)\)（\(N, K \le 5000\) なので最大 \(2.5 \times 10^7\) 回程度の単純な演算で、十分高速）
• 空間計算量: \(O(N)\)（\(j\) について 1 段前しか使わないので 2 本の配列を使い回せる。素直に 2 次元配列を取ると \(O(NK)\) で、\(5000 \times 5000 \times 8\) バイト \(= 200\) MB となりメモリ制限に触れる可能性があるため、使い回しが安全）

実装のポイント

• 添字のはみ出し：\(i - D - 1\) が負になる場合は \(0\) にクランプします（idx = max(i-D-1, 0)）。\(dp[\cdot][0] = 0\) なので、これで「それ以前に働いた日がない」ケースを自然に扱えます。

• \(D = 0\) のケース：このとき参照先は \(dp[j-1][i-1]\) となり、連続する日に働けることが正しく表現されます。特別扱いは不要です。

• オーバーフロー：\(A_i \le 10^9\)、最大 \(5000\) 日なので合計は最大 \(5 \times 10^{12}\) になります。long long（64bit 整数）を使いましょう。

• 配列の使い回し：prev（\(j-1\) 段目）と cur（\(j\) 段目）を用意し、\(j\) のループの最後で swap します。cur[0] = 0 の初期化を毎回忘れないようにしてください。

• 「\(K\) 日以下」という定義にしているため、間隔制約のせいで \(K\) 日働けない場合でも自動的に正しい答えになります（dp[j][i-1] からの遷移が「働く回数を余らせる」ことを許すため）。

  ソースコード

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,K,D;
    if(scanf("%d %d %d",&N,&K,&D)!=3) return 0;
    vector<long long> A(N+1);
    for(int i=1;i<=N;i++) scanf("%lld",&A[i]);
    vector<long long> prev(N+1,0), cur(N+1,0);
    // prev = dp[0][*] = 0
    for(int j=1;j<=K;j++){
        cur[0]=0;
        for(int i=1;i<=N;i++){
            int idx = i-D-1; if(idx<0) idx=0;
            long long v = prev[idx]+A[i];
            long long w = cur[i-1];
            cur[i] = v>w?v:w;
        }
        swap(prev,cur);
    }
    printf("%lld\n", prev[N]);
    return 0;
}

---

この解説は claude5opus-high によって生成されました。