DA-S95-CA3-7
Time Limit: 20 Seconds Memory Limit: 32768 KB
یکی از کاربردهای مهم علوم کامپیوتر در زیست‌شناسی پیدا کردن شباهت بین گونه‌های مختلف جانداران است. برای این کار DNA دو جاندار رو به عنوان دو رشته در نظر میگیرند و در این صورت هر ترکیب بازی موجود در DNA به یک کاراکتر تشبیه می‌شود. مثلا اگر قسمتی از DNA شامل ترکیب‌های Guanine، Adenine، Cytosine و Guanine باشد آن را با یک رشته‌ی چهار حرفی GACG نشان می‌دهیم. با این تبدیل، برای پیدا کردن شباهت دو DNA و ترکیب‌های آنها، شباهت میان رشته‌ها مورد بررسی قرار می‌گیرد و همانطور که مشخص است رشته‌ی GACC شباهت بیشتری نسبت به CACC به رشته‌ی اول دارد. یکی از معیارها برای بیان شباهت میان رشته‌ها، فاصله‌ی همترازی (alignment) دو رشته است. برای این منظور بین کاراکترهای هر رشته می‌توان فاصله اضافه کرد تا حروف یکسان رشته‌ها در یک جایگاه قرار بگیرند. برای مثال همترازی دو رشته‌ی CGCT و CGT به این صورت خواهد بود: (خط‌های سبز تطابق را نشان می‌دهند) CGCT || | CG-T در این همترازی در مجموع یک فاصله اضافه شده است. برای اضافه کردن هر فاصله به هرکدام از رشته‌ها جریمه‌ی s درنظر گرفته می‌شود و اگر دو حرف با هم تطابق داشته باشند امتیاز ۱۰ به همترازی اضافه می‌شود. با فرض s=1 امتیاز همترازی بالا ۲۹ است. همچنین امکان دارد دو حرف در جایگاهی از هر دورشته یکسان نباشند، در این صورت جریمه‌ی عدم تطابق d کم می‌شود. برای مثال اگر دو رشته‌ی CGAC و CGTC را داشته باشیم و s=1 و d=1 باشد بهترین همترازی امتیاز ۲۹ دارد و به این شکل است: (خط قرمز نشان‌دهنده‌ی عدم تطابق حروف هستند) CGAC |||| CGTC همچنین اگر s=1 و d=5 باشد بهترین همترازی امتیاز ۲۸ دارد و به این صورت می‌شود: CG-AC || | CGT-C مشکلی که روش‌های معمول برای یافتن همترازی دو رشته دارند استفاده زیاد آنها از حافظه‌است، DNAها اندازه‌ی بزرگی دارند و برای مثال اندازه DNA انسان حدود 3 * 109 است. به همین دلیل برای بدست آوردن بهترین همترازی دو رشته با روش برنامه‌نویسی پویا دچار محدودیت حافظه خواهیم شد و در عمل از روش‌های تقسیم و غلبه برای حل این مسئله استفاده می‌شود. الف) برای پیدا کردن بیشترین امتیاز همترازی بین دورشته به طول n و m (که ملاکی برای شباهت بین DNAها است) با روش تقسیم و غلبه روشی با زمان O(mn) ارائه دهید که حافظه‌ی مصرفی آن O(min{m,n}) باشد. (از این روش در مسئله‌ی بعد استفاده می‌شود) ب) روشی که در قسمت «الف» ارائه کرده‌اید را به یکی از زبان‌های C++ یا جاوا پیاده سازی کنید.Input
در خط اول تعداد تست‌کیس‌ها قرار دارد و برای هر تست‌کیس ابتدا n و m که طول رشته‌ها هستند قرار دارد و بعد از آن s و d قرار دارند. سپس در دو خط بعد دو رشته قرار دارند.Output
برای هر تست‌کیس در خروجی یک که امتیاز بهترین همترازی دو رشته است را بنویسید.Sample Input
2 4 4 1 1 CGAC CGTC 4 4 1 5 CGAC CGTC
Sample Output
29 28Submit