سؤال ۲۸
ترکیب دو دنباله‌ی مرتب $A$ و $B$ به ترتیب با اندازه‌های $n$ و $m$ یک دنباله‌ی مرتب به اندازه‌ی $n+m$ تولید می‌کند و این کار به اندازه‌ی $m+n$ هزینه دارد. (مثلاً اگر $A=(1,2,3,5)$ و $B=(4,6)$ باشد $C=(1,2,3,4,5,6)$ ترکیب این دو دنباله و هزینه‌ی تولید آن ۶ است). برای ترکیب سه دنباله، ابتدا دو تای آن‌ها را باهم ترکیب و دنباله‌ی حاصل را با دنباله‌ی سوم ترکیب می‌کنیم. بدیهی است که انتخاب دو دنباله‌ی اول در کل هزینه‌ی ترکیب مؤثر است. حال فرض کنید ۷ دنباله به‌اندازه‌های ۴، ۵، ۶، ۷، ۸، ۸، و ۱۰ داریم. کم‌ترین هزینه‌ی کل برای ترکیب این ۷ دنباله چه قدر است؟
- ۴۸
- ۱۰۵
- ۱۳۴
- ۱۴۴
- ۱۶۲
پاسخ
گزینه (۳) درست است.
ابتدا توجه می‌کنیم که برای ترکیب سه دنباله با طول‌های $a$،$b$ و $c$ ابتدا دو تا از آن‌ها مانند $a$،$b$ را ترکیب کرده(که حاصل دنباله به طول $a+b$ و با هزینه $a+b$ می‌شود) و سپس دنباله‌های حاصل را با دنباله سوم ترکیب می‌کنیم که حاصل دنباله‌ای به طول $a+b+c$ شده ولی هزینه آن $(a+b)+c$ می‌شود که در کل مجموع هزینه‌ها برابر $2(a+b)+c$ می‌شود. برای آن که کل هزینه‌ها مینیمم شود کافی است هر یکاز دو عدد $a$ و $b$ از عدد $c$ کم‌تر یا مساوی باشند. بنابراین در هر دسته‌ای که حداقل ۳ دنباله داشته باشد ابتدا دنباله‌های با طول مینیمم را با هم ترکیب می‌کنیم٬ که به جدول زیر خواهیم رسید:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
