Overview

This is a dynamic programming (DP) problem where you visit towns along a highway while satisfying movement restrictions and budget constraints to maximize profit.

Analysis

Problem Summary

• \(N\) towns are lined up in a row
• Each town has a profit \(A_i\) and accommodation cost \(B_i\)
• Towns visited must satisfy “the difference between adjacent town numbers is at most \(K\)”
• The total accommodation cost must be at most \(M\) yen

Key Observations

1. The visiting order is always from west to east (from smaller to larger town numbers). This is because the constraint applies to the sequence of visited towns when arranged in order.

2. If we know “the last town visited” and “the accommodation cost spent,” we can make optimal choices from there. This is a typical DP state design.

3. The condition for moving from town \(i\) to town \(j\) is:

   • \(i < j\) (moving east)
   • \(j - i \leq K\) (movement distance is at most \(K\))

Issues with the Naive Approach

Enumerating all visiting patterns for towns would give \(2^N\) combinations, which is far too slow for \(N = 200\).

Solution Using DP

By maintaining “the last town visited” and “the total accommodation cost spent” as states, we can solve this efficiently.

Algorithm

DP Definition

\(dp[i][c]\) = maximum profit when town \(i\) is the last visited town and the total accommodation cost is exactly \(c\)

The initial value is \(-\infty\) (representing unreachable states).

Initialization

When choosing each town \(i\) as “the first town to visit”: $\(dp[i][B_i] = A_i \quad (when\ B_i \leq M)\)$

Transitions

When moving from town \(i\) to town \(j\) (\(i < j\), \(j - i \leq K\)):

\[dp[j][c + B_j] = \max(dp[j][c + B_j], dp[i][c] + A_j)\]

Transitions are only possible when \(c + B_j \leq M\).

Concrete Example

For \(N=3, M=5, K=2\) with town information \((A_1, B_1) = (10, 2), (A_2, B_2) = (20, 3), (A_3, B_3) = (15, 2)\):

1. Initialization: \(dp[0][2]=10, dp[1][3]=20, dp[2][2]=15\)
2. From town 0 to town 1: \(dp[1][2+3]=dp[1][5]=10+20=30\)
3. From town 0 to town 2: \(dp[2][2+2]=dp[2][4]=10+15=25\)
4. From town 1 to town 2: \(dp[2][3+2]=dp[2][5]=20+15=35\)

The answer is \(\max(dp[i][c]) = 35\)

Finding the Answer

Take the maximum of all \(dp[i][c]\) values. Also consider the case of visiting no towns (profit 0).

Complexity

• Time complexity: \(O(N^2 \times M)\)
  • Each combination of town \(i\) and accommodation cost \(c\) is \(O(N \times M)\)
  • From each state, transition to at most \(K\) towns (at most \(N\) towns)
• Space complexity: \(O(N \times M)\)
  • Size of the DP table

Implementation Notes

1. Managing unreachable states: Use INF = float('-inf') and do not transition from unreached states

2. Transition range: Use range(i + 1, min(i + K + 1, N)) to explore only towns within \(K\) distance from town \(i\)

3. Initial value for the answer: Start with profit \(0\) (case of visiting no towns) and compare with all DP values

4. Checking accommodation cost limit: Don’t forget to verify the condition new_cost <= M

Source Code

def solve():
    N, M, K = map(int, input().split())
    towns = []
    for _ in range(N):
        a, b = map(int, input().split())
        towns.append((a, b))
    
    # dp[i][c] = maximum profit when the last visited town is i and accommodation cost spent is c
    # However, we also need to consider the state where town i has not been visited
    
    # dp[i][c] = maximum profit when town i is the last visited and total accommodation cost is exactly c
    # -1 represents unreachable
    
    INF = float('-inf')
    
    # dp[i][c]: maximum profit when town i is the last visited town and total accommodation cost is c
    dp = [[INF] * (M + 1) for _ in range(N)]
    
    # Initialization: visiting each town as the first town
    for i in range(N):
        a, b = towns[i]
        if b <= M:
            dp[i][b] = a
    
    # Transition: move from town i to town j (i < j, j - i <= K)
    for i in range(N):
        for c in range(M + 1):
            if dp[i][c] == INF:
                continue
            # Town j reachable from town i
            for j in range(i + 1, min(i + K + 1, N)):
                a_j, b_j = towns[j]
                new_cost = c + b_j
                if new_cost <= M:
                    dp[j][new_cost] = max(dp[j][new_cost], dp[i][c] + a_j)
    
    # Answer: maximum of all dp[i][c], or 0 (case of visiting no towns)
    ans = 0
    for i in range(N):
        for c in range(M + 1):
            if dp[i][c] != INF:
                ans = max(ans, dp[i][c])
    
    print(ans)

solve()

---

This editorial was generated by claude4.5opus.