ก่อนอื่น เราจะโมเดลโจทย์เป็นกราฟมีทิศทาง โดยให้จุดยอดแต่ละจุดแทนชั้น และเส้นเชื่อมแต่ละอันแทนสไลเดอร์ที่เชื่อมระหว่างชั้น กราฟที่จะได้มานั้นจะมี $N$ จุดยอด โดยที่จะมีเส้นเชื่อมน้ำหนัก $C$ ที่เชื่อม $i$ ไปหา $j$ ถ้า $i> j$

จากนั้นเราจะสร้างจุดยอดพิเศษ $s$ โดยที่มีเส้นเชื่อมจาก $s$ ไปหาจุดยอด $i$ ใด ๆ ให้มีน้ำหนักเป็น $a_i$ และเราจะสร้างจุดยอดพิเศษ $t$ โดยที่มีเส้นเชื่อมจากจุดยอด $i$ ใด ๆ ที่ไม่ใช่ $s$ ไปหา $t$ และมีน้ำหนักเป็น $b_i$

เมื่อเราสร้างกราฟเสร็จ ให้เรามองน้ำหนักของเส้นเชื่อมเป็นความจุของเส้นเชื่อมแทน จะได้ว่าคำตอบของโจทย์ข้อนี้จะมีค่าเท่ากับ maximum flow ระหว่างจุดยอด $s$ ไปหา $t$ นั่นเอง

แต่เนื่องจากกราฟของเรามี จุดยอด $\mathcal{O}(N)$ จุด และมีเส้นเชื่อม $\mathcal{O}(N^2)$ เส้น อัลกอริธึมในการหา maximum flow ทั่ว ๆ ไปจะทำงานไม่ทัน ยกตัวอย่างเช่น

• Ford-Fulkerson algorithm ใช้เวลา $\mathcal{O}(E\max|F|) = \mathcal{O}(N^2C)$ ไม่ทันเวลา
• Edmonds-Karp algorithm ใช้เวลา $\mathcal{O}(VE^2) = \mathcal{O}(N^5)$ ไม่ทันเวลา
• Dinic's algorithm ใช้เวลา $\mathcal{O}(V^2E) = \mathcal{O}(N^4)$ ไม่ทันเวลา

หรือแม้แต่ Orlin's Algorithm ที่ทำงานได้เร็วมากในเวลา $\mathcal{O}(VE) = \mathcal{O}(N^3)$ ก็จะยังทำงานไม่ทัน

ดังนั้นเราควรจะหาวิธีอื่นในการแก้ปัญหานี้

ก่อนอื่น เรารู้ว่าค่าของ maximum flow จะมีค่าเท่ากับ minimum cut ตาม max-flow min-cut theorem ดังนั้นถ้าเราหาค่า minimum cut ในกราฟนี้ได้ เราก็จะได้คำตอบเลย

ปกติแล้วในการหา minimum cut เราจะหาจากการหา maximum flow แต่ด้วยโครงสร้างกราฟของโจทย์ข้อนี้ การหา minimum cut นั้นง่ายกว่า maximum flow มาก

ในการหา minimum cut เราจะให้ $dp[i][k]$ แทน minimum cut ตั้งแต่ชั้นที่ $i$ ถึง $N$ โดยมีจุดยอดตั้งแต่ $1$ ถึง $i-1$ ที่เมื่อมาถึงแล้วสามารถพาออกไปหา $t$ ได้ทั้งหมด $k$ จุดยอด

สำหรับ base case เราจะให้ $dp[N][k] = \min(a_N, b_N+kC)$ เทอมแรกคือการตัดเส้นเชื่อมฝั่งขาเข้าเท่านั้น และเทอมหลังคือการตัดเส้นเชื่อมฝั่งขาออกเท่านั้น โดยจะต้องจ่ายเพิ่มอีก $kC$ ในการตัดเส้นเชื่อมที่จะพาไปจุดยอดที่หลงเหลือไว้ด้วย

สำหรับการ transition ใน general case จาก $dp[i][k]$ เราจะพิจารณาทั้งหมด 3 กรณี

• ตัดเส้นเชื่อมแค่ฝั่งขาเข้าอย่างเดียว สำหรับกรณีนี้ เราไม่จำเป็นต้องตัดเส้นเชื่อม $k$ เส้น แต่ในชั้นถัดไป จุดยอดนี้สามารถเป็นทางผ่านในการเดินทางไปหา $t$ ได้ $k$ จึงจะมีค่าเพิ่มขึ้น ค่าใช้จ่ายในกรณีนี้คือ $a_i+dp[i+1][k+1]$
• ตัดเส้นเชื่อมฝั่งขาออกอย่างเดียว ในกรณีนี้เราต้องตัดเส้นเชื่อม $k$ เส้น ที่จะพาไปจุดยอดที่จะพาไปหา $t$ แต่ในที่นี้จุดยอดนี้จะไม่สามารถเป็นทางผ่านได้ เพราะเราได้ตัดฝั่งขาออกแล้ว ค่าใช้จ่ายในกรณีนี้คือ $b_i+kC+dp[i+1][k]$
• ตัดเส้นเชื่อมทั้งฝั่งขาเข้าและขาออก ในกรณีนี้จุดยอดของเราจะเป็นจุดยอดที่เป็นทางผ่านได้ก็ต่อเมื่อเรามีจุดยอดทางผ่านอยู่แล้วอย่างน้อยหนึ่งจุด นั่นคือ $k> 0$ ดังนั้นค่าใช้จ่ายในกรณีนี้คือ $a_i+b_i+dp[i+1][k+(k>0)]$ โดยเทอม $(k>0)$ จะเท่ากับ $1$ ถ้า $k>0$ มิเช่นนั้นจะเท่ากับ $0$

ดังนั้น recurrence relation ของเราคือ

เราจึงสามารถแก้ปัญหานี้ได้ในเวลา $\mathcal{O}(N^2)$