در یک مغازه‌ی عروسک‌فروشی، $n$ عروسک به ترتیب با اندازه‌های $a_1, a_2, \ldots, a_n$ ، گنجایش‌های $b_1, b_2, \ldots, b_n$ و قدمت‌های $c_1, c_2, \ldots, c_n$ وجود دارد. می‌دانیم در عروسک $i$-ام می‌توانیم حداکثر یک عروسک‌ با اندازه‌ی کم‌تر یا مساوی $b_i$ قرار دهیم ($b_i < a_i$). دقت کنید عروسک‌ها می‌توانند زنجیروار در یک‌دیگر قرار بگیرند. برای مثال عروسک ۱ در عروسک ۲ و عروسک ۲ در عروسک ۳ قرار بگیرد. اگر عروسکی را درون عروسک دیگری قرار بدهیم، برای خارج کردن عروسک درونی هزینه‌ای نمی‌پردازیم؛ زیرا مغازه‌دار متوجه نمی‌شود. برای مثال اگر عروسک ۱ درون عروسک ۲ و عروسک ۲ درون عروسک ۳ باشد، کافی است فقط هزینه‌ی عروسک ۳ را بپردازیم.

قیمت هر عروسک یک تومان است و ما تنها دو تومان پول داریم. الگوریتمی از $O(n^2)$ ارائه دهید؛ طوری که مجموع قدمت عروسک‌هایی که از مغازه خارج کرده‌ایم بیشینه شود (در صورتی که الگوریتمی از $O(n^3)$ ارائه دهید، می‌توانید تا حداکثر ۱۵ نمره بگیرید).

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