حسن یک قطعه چوب باریک و دراز به عرض $1$ و طول $l$ دارد و می‌خواهد بوسیله این چوب یک کاردستی بسازد. نمونه‌ای از شکل کاردستی که حسن می‌خواهد درست کند در شکل زیر آمده است.

می‌دانیم عرض کاردستی حسن $n$ است و ارتفاع $i$ امین برآمدگی $a_i$ است. برای مثال در شکل فوق $a_i$ ها به این شکل هستند $(3,4,2,3)$. اما او می‌خواهد با استفاده از قطعات افقی این شکل را بسازد. مانند شکل زیر:

در شکل فوق از $7$ قطعه چوب استفاده شده است. الگوریتمی از $Ο(n)$ ارائه دهید که کمترین تعداد قطعه چوب برای ساختن این کاردستی را محاسبه کند (دقت کنید شکل فوق یک برش بهینه را نشان نمی‌دهد و می‌توان شکل را با $5$ قطعه نیز پوشاند). $l$ بقدر کافی بزرگ می باشد. لازم است شبه کد پیدا کردن این مقدار را بنویسید و در مورد الگوریتم خود و درستی آن به زبان فارسی توضیح دهید.

• سوال بعد
• سوال قبل