====== سوال ۳ ======

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

{{ :سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۲۱:الگوریتم‌ها:kardasti1.png?300 |}}
می‌دانیم عرض کاردستی حسن $n$ است و ارتفاع $i$ امین برآمدگی $a_i$ است. برای مثال در شکل فوق $a_i$ ها به این شکل هستند $(3,4,2,3)$. اما او می‌خواهد با استفاده از قطعات افقی این شکل را بسازد. مانند شکل زیر:

{{ :سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۲۱:الگوریتم‌ها:kardasti2.png?300 |}}

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

  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]