toi

TOI19 energy - เติมพลังงาน (Energy)

🏠 รวมเฉลย TOI19

💎 problem.pdf

🎉 solution.cpp

ทำ Matrix Chain Multiplication ตรงๆนี้แหละ แต่เราต้องการการแบ่งที่ชั้นที่ K เราก็ทำ Matrix Chain Multiplication ทั้งหมด K ครั้ง โดนที่แต่ละครั้งให้ใช้ค่าจากชั้นก่อนเท่านั้น

dp(hi, arr[l..r]) => int # วิธีทั้งหมดที่ใช้แบ่งช่วง arr[l..r] ได้ถึง hi ชั้น
dp( 0, arr[l..r]) => 1   # ชั้นแรกไม่ต้องเปรี่ยบเทียบแบ่งกับใคร ได้ 1 วิธีเสมอ
dp(hi, arr[l..r]) => sum l..r { |pivot|
  where diff(sum(arr[l..pivot]), sum(arr[pivot..r])) < max_diff
  dp(hi-1, arr[l..pivot]) + dp(hi-1, arr[pivot..r])
}