یک مجتمع مسکونی آپارتمانی به شکل جدولی $n$ در $n$ داریم. در خانه‌ی مربعی جدول که در سطر $i$ و ستون $j$ است ساختمانی به ارتفاع $h_{i,j}$ ساخته شده است. به ساختمانی در یک مجتمع مسکونی دلباز می‌گوییم اگر هر موجودی هرچقدر قدش کوتاه باشد بتواند با ایستادن روی ساختمان بیرون مجتمع مسکونی را ببیند. یعنی بتوان از چشمش نیم-خطی موازی با زمین رسم کرد که هیچ ساختمانی را حتی در یک نقطه قطع نکند.

می‌خواهیم ارتفاع ساختمان‌ها را طوری اضافه کنیم که تمام ساختمان‌ها دلباز باشند و مجموع ساخت و ساز کمینه شود. $d_{i,j}$ را ارتفاع اضافه شده با ساختمان در سطر $i$ و ستون $j$ می‌نامیم.

الگوریتمی با $O(n^2)$ پیدا کنید که با داشتن $n$ و $h_{i,j}$ ها و $d_{i,j}$ هایی را که در شرایط مسئله صدق می‌کنند را پیدا کنید.

• سوال بعد