概要

選んだ日どうしの間隔を \(D+1\) 日以上空けながら、最大 \(K\) 日のアルバイトで得られる給料の合計を最大化します。「何日目まで考えたか」と「何日まで働けるか」を状態とする動的計画法で解きます。

考察

給料の高い日から選ぶだけではうまくいかない

ある日に働くと、その後 \(D\) 日間は働けません。そのため、給料の高い日を選んだ結果、ほかの有利な日を選べなくなる場合があります。

例えば、\(N=3,\ K=2,\ D=1\)、給料が \((6,10,6)\) の場合を考えます。

• 給料が最大の \(2\) 日目を選ぶと、\(1\) 日目とも \(3\) 日目とも両立できず、合計は \(10\) 円です。
• \(1\) 日目と \(3\) 日目を選ぶと、合計は \(12\) 円になります。

したがって、給料の高い順に選ぶ貪欲法では正解できません。また、働く日の組合せをすべて調べる方法は最大 \(2^N\) 通りあり、間に合いません。

最後の日に働くかどうかで分ける

\(1\) 日目から \(i\) 日目までの計画を考えると、次の \(2\) 通りに分けられます。

• \(i\) 日目に働かない：\(i-1\) 日目までの最適な計画をそのまま使う。
• \(i\) 日目に働く：それ以前に働けるのは \(i-D-1\) 日目までなので、その範囲の最適な計画に \(A_i\) を加える。

このように、短い期間に対する答えを利用する動的計画法が使えます。

実際に働ける日数には上限がある

\(m\) 日働くには、働く日どうしの間に最低 \(D\) 日の休みが必要です。よって、

\(m+(m-1)D \le N\)

を満たす必要があり、働ける日数は最大でも

\(\left\lfloor \dfrac{N+D}{D+1} \right\rfloor\)

です。これは \(1,\ 1+(D+1),\ 1+2(D+1),\dots\) 日目に働くことで達成できます。

したがって、以降は

\(K'=\min\left(K,\left\lfloor \dfrac{N+D}{D+1} \right\rfloor\right)\)

日まで考えれば十分です。コードでは、この値で K を更新しています。

アルゴリズム

1. DP の状態を定義する

\(dp[k][i]\) を、次の値とします。

\(1\) 日目から \(i\) 日目までの間に、\(k\) 日以下働いて得られる給料の合計の最大値

初期値は以下のとおりです。

• \(dp[0][i]=0\)：一度も働けない場合、給料は \(0\) 円。
• \(dp[k][0]=0\)：対象の日がない場合、給料は \(0\) 円。

2. 遷移を求める

\(k \ge 1,\ i \ge 1\) について、\(i\) 日目に働くかどうかで場合分けします。

\(i\) 日目に働かない場合

得られる最大値は \(dp[k][i-1]\) です。

\(i\) 日目に働く場合

それ以前に働けるのは \(i-D-1\) 日目までで、働ける残りの日数は \(k-1\) 日以下です。

\(j=\max(0,i-D-1)\)

とすると、得られる最大値は \(dp[k-1][j]+A_i\) です。

したがって、遷移式は

\(dp[k][i]=\max\left(dp[k][i-1],\ dp[k-1][\max(0,i-D-1)]+A_i\right)\)

となります。

すべての適切な計画は「\(i\) 日目に働かない」「\(i\) 日目に働く」のどちらかに属します。また、後者では以前の勤務日を \(i-D-1\) 日目までに制限することで、休養条件を必ず満たせます。よって、この遷移で最適値を求められます。

3. 配列を 2 本にしてメモリを削減する

\(dp[k][i]\) の計算に必要なのは、次の値だけです。

• 同じ \(k\) の直前の値 \(dp[k][i-1]\)
• \(1\) つ前の \(k\) の値 \(dp[k-1][j]\)

そこで、DP テーブル全体を保存せず、長さ \(N+1\) の配列を \(2\) 本使います。

• prev[i]：\(dp[k-1][i]\)
• cur[i]：\(dp[k][i]\)

具体的な手順は次のとおりです。

1. prev をすべて \(0\) で初期化する。
2. \(k=1,2,\dots,K'\) の順に以下を行う。
   • cur[0] = 0 とする。
   • \(i=1,2,\dots,N\) の順に、遷移式で cur[i] を計算する。
   • prev と cur を交換する。
3. 最後に prev[N] を出力する。

計算量

\(K'=\min\left(K,\left\lfloor \dfrac{N+D}{D+1} \right\rfloor\right)\) とすると、

• 時間計算量: \(O(NK')\)（最悪 \(O(NK)\)）
• 空間計算量: \(O(N)\)

各 DP 状態は定数時間で計算できます。最悪でも状態数は \(5000 \times 5000\) 程度です。

実装のポイント

• 給料の合計には long long を使う
  答えは最大 \(5000 \times 10^9=5\times 10^{12}\) になり得るため、32 ビット整数では収まりません。

• 参照先は i - D - 1
  例えば \(D=1\) のとき、\(i\) 日目に働くなら直前に働けるのは \(i-2\) 日目です。i - D ではないことに注意します。

• 日付が \(1\) より前になる場合は \(0\) にする
  max(0, i - D - 1) とすることで、以前に働ける日がない場合を \(dp[k-1][0]=0\) で扱えます。

• 「ちょうど \(k\) 日」ではなく「\(k\) 日以下」と定義する
  この定義により、初期値を \(0\) として扱えます。実際に \(k\) 日働けない短い期間でも問題ありません。

• 日付は昇順に計算する
  cur[i] は更新済みの cur[i-1] を使います。配列交換後に古い値が残っていても、cur[0] を設定し、残りを順番に上書きすれば問題ありません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, D;
    cin >> N >> K >> D;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    K = min(K, (N + D) / (D + 1));

    vector<long long> prev(N + 1, 0), cur(N + 1, 0);

    for (int k = 1; k <= K; ++k) {
        cur[0] = 0;
        for (int i = 1; i <= N; ++i) {
            int j = max(0, i - D - 1);
            cur[i] = max(cur[i - 1], prev[j] + A[i]);
        }
        prev.swap(cur);
    }

    cout << prev[N] << '\n';
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。