概要

各日の稼働・休止を選び、休止が連続しないようにしながら合計利益を最大化する問題です。最後の日が「稼働」か「休止」かの \(2\) 状態を持つ動的計画法（DP）で解きます。

考察

各日に稼働・休止の \(2\) 通りの選択があるため、すべての計画を列挙すると候補は \(2^N\) 通りになります。これでは \(N \le 10^6\) に間に合いません。

また、その日の利益だけを見て選ぶ貪欲法も正しくありません。今日の選択によって、明日にメンテナンス費用がかかるかどうかや、明日に休止できるかどうかが変わるためです。

例えば、\(N=2,\ C=10,\ A=(1,10)\) の場合を考えます。

• 初日に稼働すると、初日の利益は \(1\) です。翌日は稼働しても利益が \(10-10=0\) なので、合計利益は最大でも \(1\) です。
• 初日に休止し、翌日に稼働すると、合計利益は \(10\) です。

このように、目先の利益を優先するのが最適とは限りません。

ここで、翌日の利益と選択の可否に必要なのは、直前の日が稼働だったか休止だったかだけです。

• 前日が稼働なら、今日は稼働・休止のどちらも選べます。ただし、稼働すると費用 \(C\) がかかります。
• 前日が休止なら、今日は必ず稼働します。この場合、費用 \(C\) はかかりません。

連続稼働日数そのものは関係ありません。そこで、最後の日の状態ごとに最大利益を記録すれば十分です。

アルゴリズム

1. DP の状態

次の \(2\) つを定義します。

• \(W_i\)：\(i\) 日目までの条件を満たす計画のうち、\(i\) 日目に稼働する場合の最大合計利益
• \(R_i\)：\(i\) 日目までの条件を満たす計画のうち、\(i\) 日目に休止する場合の最大合計利益

2. 初期値

初日は前日の状態を考慮しないので、稼働すれば利益は \(A_1\)、休止すれば利益は \(0\) です。

\(W_1=A_1\)

\(R_1=0\)

3. 状態遷移

\(i \ge 2\) について考えます。

\(i\) 日目に稼働する場合

前日の状態に応じて、次の \(2\) 通りがあります。

• 前日が休止：今日の利益は \(A_i\) なので、合計は \(R_{i-1}+A_i\)
• 前日が稼働：今日の利益は \(A_i-C\) なので、合計は \(W_{i-1}+A_i-C\)

したがって、

\(W_i=\max(R_{i-1}+A_i,\ W_{i-1}+A_i-C)\)

となります。

\(i\) 日目に休止する場合

休止を連続させることはできないため、前日は必ず稼働していなければなりません。今日の利益は \(0\) なので、

\(R_i=W_{i-1}\)

となります。

これらの遷移は、各状態へ到達するすべての合法な選択を網羅しています。また、同じ状態であれば翌日以降の選択肢や追加利益は同じなので、それまでの利益が最大のものだけを残して構いません。このため、各日の最大利益を正しく求められます。

4. 答えと省メモリ化

最終日は稼働・休止のどちらでもよいため、答えは

\(\max(W_N,R_N)\)

です。

遷移に必要なのは前日の値だけなので、配列を用意する必要はありません。コードでは、working と resting にそれぞれ前日の \(W_i,\ R_i\) を保持し、各日の入力を読みながら更新しています。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

各日について定数回の計算を行います。入力も順に処理するため、\(A\) の配列を保存する必要はありません。

実装のポイント

• 更新前の値を保持する
  next_working と next_resting は、どちらも前日の状態から計算します。working を先に上書きすると休止状態の計算が誤るため、一時変数を使ってから更新します。

• 64 ビット整数を使う
  合計利益の絶対値は \(10^{15}\) 程度になる可能性があります。32 ビット整数では収まらないため、コードでは利益や費用に long long を使っています。

• 負の利益もそのまま扱う
  休止を連続させられないため、損失が出ても稼働しなければならない場合があります。DP の値を勝手に \(0\) 以上へ補正してはいけません。

• \(N=1\) も同じ処理で対応できる
  初期化後にループを実行せず、\(\max(A_1,0)\) が出力されます。計画期間外の状態を仮定する必要もありません。

  ソースコード

#include <algorithm>
#include <iostream>
using namespace std;

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

    int N;
    long long C;
    cin >> N >> C;

    long long A;
    cin >> A;

    long long working = A;
    long long resting = 0;

    for (int i = 1; i < N; ++i) {
        cin >> A;
        long long next_working = max(resting + A, working + A - C);
        long long next_resting = working;
        working = next_working;
        resting = next_resting;
    }

    cout << max(working, resting) << '\n';
    return 0;
}

---

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