Overview

This is a problem of maximizing electricity cost reduction within a budget, under the constraint that adjacent street lights cannot be selected simultaneously. This is a classic dynamic programming (DP) problem known as the “Knapsack Problem with Adjacency Constraints.”

Analysis

Problem Summary

• We want to select some of the \(N\) street lights to replace with LEDs
• Constraint 1: The total cost must not exceed the budget of \(K\) yen
• Constraint 2: Adjacent street lights (the \(i\)-th and \((i+1)\)-th) cannot be selected simultaneously
• Objective: Maximize the total reduction effect \(V_i\)

Issues with the Naive Approach

Trying all possible selections would result in \(2^N\) combinations, which is far too slow when \(N = 200\).

Key Insight

In a standard knapsack problem, we use DP to find “the maximum value obtainable with weight \(j\) after considering items up to the \(i\)-th one.” In this problem, due to the “adjacency constraint,” we need to additionally track whether the previous street light was selected or not.

Algorithm

State Definition

We use the following two arrays: - prev_not_selected[j]: Maximum reduction effect obtainable with budget \(j\) yen when the previous street light was not selected - prev_selected[j]: Maximum reduction effect obtainable with budget \(j\) yen when the previous street light was selected

Transitions

When processing the \(i\)-th street light (reduction effect \(V_i\), cost \(W_i\)):

1. When not selecting the \(i\)-th street light - It doesn’t matter whether the previous one was selected or not - curr_not_selected[j] = max(prev_not_selected[j], prev_selected[j])

2. When selecting the \(i\)-th street light - The previous one must not have been selected (adjacency constraint) - We need to pay the cost \(W_i\) - curr_selected[j] = prev_not_selected[j - W_i] + V_i (only when \(j \geq W_i\))

Concrete Example

For \(N=3\), \(K=5\) with street lights \((V_1, W_1) = (10, 2)\), \((V_2, W_2) = (20, 3)\), \((V_3, W_3) = (15, 2)\):

• Cannot select both the 1st and 2nd (adjacent)
• Selecting the 1st and 3rd: cost \(2+2=4 \leq 5\), reduction effect \(10+15=25\)
• Selecting only the 2nd: cost \(3\), reduction effect \(20\)

Therefore, the answer is \(25\).

Initialization and Answer

• Initial state: Before looking at the 0th street light, nothing is selected, budget is 0, and reduction effect is 0
• Answer: After processing all street lights, the maximum reduction effect for budgets \(0 \sim K\)

Complexity

• Time Complexity: \(O(NK)\)
  • For each of the \(N\) street lights, we update states for budgets \(0 \sim K\)
• Space Complexity: \(O(K)\)
  • We only need to maintain arrays for “previous state” and “current state”

Implementation Notes

1. Managing unreachable states: Use \(-1\) (INF) as a value and do not transition from such states

2. Array updates: Calculate the current state (curr_*) from the previous state (prev_*), then swap them after processing

3. Initial state setup: Start from prev_not_selected[0] = 0 (nothing selected, budget 0, reduction effect 0)

4. Final answer: Search for the maximum value from both prev_not_selected and prev_selected (since the last street light may or may not be selected)

Source Code

def solve():
    N, K = map(int, input().split())
    lights = []
    for _ in range(N):
        v, w = map(int, input().split())
        lights.append((v, w))
    
    # dp[i][j] = maximum reduction effect when considering up to the i-th street light and using j yen of budget
    # State: we also need to consider whether the last street light was selected
    # dp[i][j][0] = maximum reduction effect when not selecting the i-th
    # dp[i][j][1] = maximum reduction effect when selecting the i-th
    
    # Initialization: -1 represents unreachable (since reduction effect is non-negative, we can use -1 for detection)
    INF = -1
    
    # dp[j][0] = maximum reduction effect with budget j when not selecting current street light
    # dp[j][1] = maximum reduction effect with budget j when selecting current street light
    
    # Initial state
    prev_not_selected = [0] + [INF] * K  # Nothing selected, budget 0, reduction effect 0
    prev_selected = [INF] * (K + 1)  # Nothing selected yet
    
    # Process from the 0th street light
    for i in range(N):
        v, w = lights[i]
        
        curr_not_selected = [INF] * (K + 1)
        curr_selected = [INF] * (K + 1)
        
        for j in range(K + 1):
            # When not selecting the i-th
            # It doesn't matter whether the previous street light was selected or not
            if prev_not_selected[j] != INF:
                if curr_not_selected[j] < prev_not_selected[j]:
                    curr_not_selected[j] = prev_not_selected[j]
            if prev_selected[j] != INF:
                if curr_not_selected[j] < prev_selected[j]:
                    curr_not_selected[j] = prev_selected[j]
            
            # When selecting the i-th
            # The previous street light must not have been selected
            if j >= w and prev_not_selected[j - w] != INF:
                new_val = prev_not_selected[j - w] + v
                if curr_selected[j] < new_val:
                    curr_selected[j] = new_val
        
        prev_not_selected = curr_not_selected
        prev_selected = curr_selected
    
    # Find the maximum value
    ans = 0
    for j in range(K + 1):
        if prev_not_selected[j] != INF:
            ans = max(ans, prev_not_selected[j])
        if prev_selected[j] != INF:
            ans = max(ans, prev_selected[j])
    
    print(ans)

solve()

---

This editorial was generated by claude4.5opus.