กำหนดให้ $H_{i, j}$ เป็นความสูงของช่อง $(i, j)$

ในข้อนี้ เราจะสามารถหาคำตอบได้ด้วยการใช้ Dynamic Programming โดยกำหนดให้ $dp(i, j)$ เป็นพลังงานที่น้อยที่สุดที่ใช้ในการกระโดดจาก $(1, 1)$ มายัง $(i, j)$

ในการกระโดดมายังช่อง $(i, j)$ เราสามารถแบ่งออกเป็น 2 กรณีดังที่โจทย์กำหนดมาคือ

1. กระโดดในแนวแถวจากช่อง $(i, k)$ เมื่อ $k < j$
2. กระโดดในแนวคอลลัมน์จากช่อง $(k, j)$ เมื่อ $k < i$

การหาค่า $dp(i, j)$ สามารถทำได้โดยกำหนดให้ $dp(1, 1) := 0$ เป็น Base Case และสำหรับ $dp(i, j)$ ใด ๆ จะได้ว่าดังนี้

สำหรับกรณีที่ 1 เราจะได้ว่า $dp(i, j) = \min \limits_{1 \leq k < j, H_{i, k} < H_{i, j}} \{dp(i, k) + \sum \limits_{l = k + 1}^{j - 1} H_{i, l}\}$

สำหรับกรณีที่ 2 เราจะได้ว่า $dp(i, j) = \min \limits_{1 \leq k < i, H_{k, j} < H_{i, j}} \{dp(k, j) + \sum \limits_{l = k + 1}^{i - 1} H_{l, i}\}$

เราจะเลือกกรณีที่ทำให้ $dp(i, j)$ มีค่าน้อยที่สุด แล้วคำตอบสุดท้ายของโจทย์จะเป็น $dp(R, C)$

หากเราทำตาม Recurrence Formula ด้านบนนี้ตรง ๆ จะไม่ทันเวลาที่โจทย์ได้กำหนดไว้ ดังนั้นเราจึงต้องทำ Optimization โดยวิธีดังต่อไปนี้จะอธิบายเฉพาะกรณีที่ 1 เท่านั้นเนื่องจากทั้งสองกรณีใช้วิธีที่คล้ายคลึงกัน

การหาผลรวม $\sum \limits_{l = k + 1}^{j - 1} H_{i, l}$ เราสามารถลดเวลาการทำงานได้โดย กำหนดให้ $pref_{i, j} = \sum \limits_{k = 1}^{j} H_{i, k}$ หรือ Prefix Sum ของแต่ละแถวนั่นเอง ผลรวมดังกล่าวจะมีค่าเท่ากับ $pref_{i, j - 1} - pref_{i, k}$ ซึ่งลดเวลาการทำงานเป็น $O(1)$ เท่านั้น แต่ก็นังไม่เพียงพอที่จะทำให้ทำงานทันภายในเวลา

พิจารณาเฉพาะแถว $i$ สังเกตว่าค่า $pref_{i, j - 1}$ จะถูกรวมในพลังงานที่ใช้เสมอ ดังนั้นจะได้ว่า $dp(i, j) = \min \limits_{1 \leq k < j, H_{i, k} < H_{i, j}} \{dp(i, k) - pref_{i, k}\} + pref_{i, j - 1}$ เราจึงจำเป็นต้องสนใจเพียงค่าของ $dp(i, k) - pref_{i, k}$ เท่านั้น

และจากเงื่อนไขของโจทย์ที่ว่า $H_{i, k} < H_{i, j}$ เราจึงต้องทำ Coordinate Compression บนค่า $H_{i, j}$ เมื่อ $1 \leq j \leq C$ เก็บในอาร์เรย์ $coord$ เมื่อสมาชิกเรียงจากน้อยไปมาก แล้วใช้ Segment Tree ที่รองรับการหาค่าที่น้อยที่สุดในช่วง เก็บค่า $dp(i, j)$ ทำให้เราสามารถหาค่า $dp(i, j)$ ภายใน $\mathcal{O}(\log C)$ ได้

นอกจากนี้ เราจะพิจารณาค่า $dp(i, j)$ จาก $j = 1, 2, \dots, C$ และสำหรับ $dp(i, j)$ ที่ยังไม่ได้หาค่า จะกำหนดให้เป็น $\infty$ ก่อน เพื่อให้ตรงตามเงื่อนไขที่ว่า $k < j$ เสมอ

วิธีดังกล่าวนี้ สามารถนำไปปรับใช้ในการกระโดดกรณีที่ 2 ได้ ทำให้ใช้ Segment Tree ทั้งหมด $R + C$ ต้น และทำการ Coordinate Compression ทั้งหมด $R + C$ ครั้ง

Time Complexity: $\mathcal{O}(RC \log RC)$