المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:متفرقه:سوال ۲۹

بسته‌بندی

یک جعبه‌ی $n$ بعدی را در نظر بگیرید که توسط ابعاد آن مشخص می‌شود. می‌خواهیم بلند‌ترین رشته مثل $b_1,b_2,...,b_k$ از این جعبه‌ها را بیابیم که در آن هر جعبه‌ی $b_i$ بتواند داخل جعبه‌ی $b_{i+1}$ قرار گیرد $(1\leq i \leq k)$. می‌گوییم جعبه‌ی $(d_1,d_2,...,d_n)$ در $)e_1,e_2,...,e_n)$ قرار می‌گیرد، اگر جایگشتی از $d_i$ ها مثل $d_{i_1},d_{i_2},...,d_{i_n}$ موجود باشد به طوری که به ازای $(1\leq j \leq n)$ داشته باشیم $d_{i_j}\leq e_j$.


ابزار صفحه