Overview

Given \(N\) street lights, select some of them to replace with LEDs within a budget of \(K\) yen, maximizing the total annual electricity cost reduction. However, two adjacent street lights cannot be replaced at the same time.

Analysis

This problem can be thought of as an application of the knapsack problem. Each street light has a “value” (reduction effect \(V_i\)) and a “weight” (cost \(W_i\)), and we need to select items that fit into a knapsack with capacity \(K\) (the budget).

However, this is not a simple knapsack problem — there is the additional constraint that “two adjacent items cannot be selected simultaneously.” This means that when using dynamic programming (DP), we need to keep track of the previous selection.

For example, the following naive DP approach would fail: - dp[i][k] := the maximum effect when considering up to the \(i\)-th light with total cost at most \(k\)
With this formulation, we cannot tell “whether the \((i-1)\)-th light was selected,” so we cannot enforce the adjacency constraint.

Therefore, we add a state to the DP table indicating “whether the previous light was selected”: - dp[i][k][last] := the maximum effect when considering up to the \(i\)-th light, with total cost at most \(k\), and whether the previous (\((i-1)\)-th) light was selected (last = 1 or 0)

By maintaining this state, we can implement the transition rule: “if \((i-1)\) was selected, then \(i\) cannot be selected.”

Additionally, to reduce space complexity, we use rolling DP (a space optimization technique) that only keeps the current and previous states.

Algorithm

We solve this using dynamic programming (DP).

DP Table Definition

• dp[k][last] := the maximum reduction effect when the current total cost is at most \(k\) and the previous street light was either selected (last = 1) or not selected (last = 0)

Initialization

• For the first street light (\(i = 0\)):
  • If selected: dp[W[0]][1] = V[0] (if within budget)
  • If not selected: dp[k][0] = 0

Transitions

Update sequentially from \(i = 1\) to \(N - 1\): - Do not select the \(i\)-th light: - curr_dp[k][0] = max(prev_dp[k][0], prev_dp[k][1]) - Select the \(i\)-th light (only if \(k \geq W[i]\) and transitioning from prev_dp[k - W[i]][0]): - curr_dp[k][1] = max(curr_dp[k][1], prev_dp[k - W[i]][0] + V[i])

Answer

• In the final state, take the maximum of max(dp[k][0], dp[k][1]) over all \(k = 0\) to \(K\).

Complexity

• Time complexity: \(O(N \cdot K)\)
• Space complexity: \(O(K)\)

※ Rolling DP significantly reduces the space usage.

Implementation Notes

• By using only prev_dp and curr_dp to update the DP table, we reduce space complexity.
• To satisfy the “no adjacent selection” constraint, we introduce the last state and carefully manage the transitions.
• Don’t forget to take the maximum over the entire cost range at the end (checking both dp[k][0] and dp[k][1]).

## Source Code

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    
    V = [0] * N
    W = [0] * N
    
    for i in range(N):
        V[i] = int(data[2 + 2*i])
        W[i] = int(data[3 + 2*i])
    
    # dp[i][k][last] := i番目まで見て、コストがk以下で、i-1番目を選んだかどうか(last=1:選んだ, 0:選んでない)時の最大効果
    # ただし、last == 1 のとき i-1番目を選んでいるので i番目は選べない。
    # 配列を毎回確保するとメモリが足りるか怪しいので、空間削減したDPを行う。
    
    # dp[k][last] := コストがk以下で、直前を選んだかどうか(last=1:選んだ, 0:選ばない)時の最大効果
    prev_dp = [[0]*2 for _ in range(K+1)]
    
    # 初期状態: 0番目を考える
    # 0番目を選ばない: dp[k][0] = 0
    # 0番目を選ぶ:     dp[w0][1] = v0 (w0 <= K)
    curr_dp = [[0]*2 for _ in range(K+1)]
    if W[0] <= K:
        curr_dp[W[0]][1] = V[0]
    for k in range(K+1):
        curr_dp[k][0] = 0
    
    prev_dp = curr_dp
    
    # i=1 から N-1まで処理
    for i in range(1, N):
        curr_dp = [[0]*2 for _ in range(K+1)]
        w = W[i]
        v = V[i]
        for k in range(K+1):
            # i番目を選ばない場合
            curr_dp[k][0] = max(prev_dp[k][0], prev_dp[k][1])
            
            # i番目を選ぶ場合（予算内かつ前のが選ばれていない）
            if k >= w:
                curr_dp[k][1] = max(curr_dp[k][1], prev_dp[k-w][0] + v)
        
        prev_dp = curr_dp
    
    # 最終的な答えは max(dp[K][0], dp[K][1])
    res = 0
    for k in range(K+1):
        res = max(res, prev_dp[k][0], prev_dp[k][1])
    print(res)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.