اتاقی به شکل یک جدول $n\times n$ داریم که در برخی از خانه‌های آن مجسمه قرار دارد! بیرون اتاق $2n$ میله(خیلی بلند) تعبیه شده است که $n$ تای آن‌ها به صورت عمودی بالای $n$ ستون جدول و $n$تای دیگر به صورت افقی سمت راست سطرهای جدول می‌باشند. می‌خواهیم بیش‌ترین مساحت اتاق را با وارد کردن قسمتی از میله‌ها(در همان راستا) به داخل جدول بپوشانیم به طوری که هیچ دو میله‌ای هم دیگر را قطع نکنند و میله‌ها از مجسمه‌ها رد نشوند!

شما بایستی الگوریتمی با زمان اجرای $O(n^3)$ طراحی کنید که بیش‌ترین مساحتی را از اتاق پیدا کند که می‌توان با میله‌ها پوشاند و همچنین طول قسمتی را از هر میله که وارد اتاق می‌شود مشخص کند.

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