概要

\(N\) 個の仕事からいくつか選び、連続する番号のペアごとにコスト \(K\) が引かれるとき、得られる利益の最大値を求めます。

考察

この問題では、単純に報酬の高い仕事を貪欲に選ぶだけでは最適解を得られません。
なぜなら、連続する番号の仕事を選ぶとペナルティ \(K\) がかかるため、利益を最大化するためには「どの仕事を選ぶか」だけでなく、「ペナルティをどれだけ抑えるか」も考慮する必要があります。

例えば、以下のような入力を考えます：

N=3, K=5
A = [10, 8, 10]

仕事1と3を選ぶと、報酬は \(10 + 10 = 20\) でペナルティは \(0\) なので利益は \(20\)。
一方、全ての仕事を選ぶと報酬は \(28\) ですが、ペナルティが \(2K = 10\) かかり、利益は \(18\) になります。
このように、貪欲に選んでも最適とは限りません。

そこで、動的計画法（DP）を用いて、「仕事 \(i\) まで見たときに、仕事 \(i\) を選ぶか選ばないか」に基づく最適な選択を逐次的に求めることにします。

アルゴリズム

動的計画法（DP）を用います。

DPテーブルの定義

dp[i][0]: 仕事 \(i\) を選ばないときの、仕事 \(1\) から \(i\) までの範囲での最大利益
dp[i][1]: 仕事 \(i\) を選ぶときの、同様の最大利益

遷移

仕事 \(i+1\) に対して以下の遷移を行います：

• 仕事 \(i+1\) を選ばない場合：
  dp[i+1][0] = max(dp[i][0], dp[i][1])
  → 前の状態のどちらからも遷移可能

• 仕事 \(i+1\) を選ぶ場合：
  dp[i+1][1] = max(dp[i][0] + A[i], dp[i][1] + A[i] - K)
  → 前の仕事 \(i\) を選んでいた場合はペナルティ \(K\) を引く

初期条件は： - dp[0][0] = 0 （何も選んでいない状態） - dp[0][1] = -∞ （無効な状態）

最後に max(dp[N][0], dp[N][1]) が答えになります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)
  （ただし、dpテーブルを2変数でローリングすることで空間計算量を \(O(1)\) にすることも可能）

実装のポイント

• DPの添字に注意（1-indexedなのか0-indexedなのか）
• 初期状態で dp[0][1] を -inf にしておくことで、不正な遷移を防ぐ
• 入力を高速に読み込むために sys.stdin.read を使用している

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # dp[i][0]: 仕事iを選ばないときの最大利益
    # dp[i][1]: 仕事iを選ぶときの最大利益
    dp = [[0]*2 for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = -float('inf')  # 無効な状態

    for i in range(N):
        # 仕事i+1を選ばない
        dp[i+1][0] = max(dp[i][0], dp[i][1])
        # 仕事i+1を選ぶ
        # 前の仕事を選んでいた場合は-Kのペナルティ
        dp[i+1][1] = max(dp[i][0] + A[i], dp[i][1] + A[i] - K)

    result = max(dp[N][0], dp[N][1])
    print(result)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。