מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/הגשר הזבלה/שאלה

מעל הירקון עומד גשר שאורכו $m$ מטרים ($m$ מספר שלם חיובי גדול מ1 כלשהו). הגשר נמצא לא תקין אפילו בסטנדרטים של מדינת ישראל(!). יש לפרק את הגשר לחלקים ולפנותו בצורה הזולה ביותר. ראשית צריך לשבור את הגשר. ניתן לשבור את הגשר למספר חלקים. שבירת הגשר חייבת להתבצע בנקודות $1,\cdots ,m-1$ בלבד. שבירת כל נקודה עולה $k$ שקלים ($k$ מספר שלם חיובי כלשהו).

תבנית:מבנה תבנית

כעת יש להוביל את חלקי הגשר. הנח שקיימת פונקציה $f$ ידועה כך ש$f(i)$ מתארת את עלות הובלתו של חלק בעל אורך i. הנח ש$f(i)$ הוא מספר שלם חיובי לכל $i$.

אנא מצא אלגוריתם יעיל למציאת נקודות השבירה כך שסך העלויות (שבירה והובלה) נמוך ככל האפשר. כלומר, אנא כתוב אלגוריתם יעיל שימצא את העלות המינימלית וכן ידפיס את נקודות השבירה של עלות זו.