مسابقه شماره ۲۳۵
سوال
ترکیب دو دنباله مرتب A و B به ترتیب با اندازه‌های n و m یک دنباله مرتب به اندازه n + m تولید می‌کند و این کار به اندازه m + n هزینه دارد.
( مثلا اگر A = ( 1,2,3,4,) و B = ( 4,6 ) باشد, C = ( 1,2,3,4,5,6 ) ترکیب این دو دنباله و هزینه تولید آن 6 است.)
برای ترکیب سه دنباله , ابتدا دوتای آنها را به هم ترکیب و دنباله حاصل را با دنباله سوم ترکیب می‌کنیم. بدیهی است که انتخاب دو دنباله اول در کل هزینه ترکیب موثر است. حال فرض کنید 7 دنباله سوم ترکیب می‌کنیم. بدیهی است که انتخاب دو دنباله اول در کل هزینه ترکیب موثر است. حال فرض کنید 7 دنباله به اندازه‌های 10,8,8,7,6,5,4 داریم. کمترین هزینه کل برای ترکیب این 7 دنباله چقدر است؟
پاسخ
ابتدا توجه می‌کنیم که برای ترکیب سه دنباله با طول‌های c,b,a ابتدا دو تا از آنها مانند , b,a را ترکیب کرده ( که حاصل دنباله به طول a + b و با هزینه a + b می‌شود) و سپس دنباله‌های حاصل را با دنباله سوم ترکیب می‌کنیم که حاصل دنباله‌ای به طول a + b + c شده ولی هزینه آن ( a + b ) + c می‌شود که در کل مجموع هزینه‌ها برابر 2( a + b) + c می‌شود. برای آنکه کل هزینه‌ها مینیمم شود کافی است هر یک از دو عدد a و b از عدد c کمتر یا مساوی باشند. بنابراین در هر دسته‌ای که حداقل 3 دنباله داشته باشد ابتدا ذنباله‌های با طول مینیمم را با هم ترکیب می‌کنیم , که به جدول زیر خواهیم رسید.