لئونارد در یک شرکت ژنتیکی استخدام شده که روی تغییر دنباله DNA گیاهان برای تولید محصولات بهتر کار میکند. یک ژن دنبالهای از حروف A
، C
، G
و T
است.
در تحقیقات اخیر مشخص شده که اگر ژن سیب، شامل ژن به صورت یک زیر رشته باشد، ماندگاری بیشتری خواهد داشت. برای رسیدن به این هدف میخواهیم تعدادی حرف در مکانهای مشخصی از ژن سیب تزریق کنیم تا در نهایت ژن نهایی شامل ژن شود (ژن را به عنوان زیررشته داشته باشد).
تزریق هر یک از چهار کاراکتر هزینهی خاصی دارد. وظیفه لئونارد یافتن مکانهای تزریق ژن و کاراکترهای هر تزریق است بهطوری که در نهایت هزینه کمینه شود. به او کمک کنید تا کمینه هزینه را محاسبه کند.
در خط اول یک رشته از کاراکتر داریم که ژن سیب را مشخص می کند. خط دوم شامل کاراکتر است که رشتهی را مشخص می کند. کاراکترها حروف انگلیسی بزرگ هستند. خط سوم شامل چهار عدد صحیح است که به ترتیبِ A
، C
، G
و T
هزینه اضافه کردن هر کاراکتر را مشخص می کند.
در یک خط کمینه هزینه را چاپ کنید.
در این مثال هزینهی اضافه کردن A
و G
برابر با ۳ و هزینهی اضافه کردن C
و T
برابر با صفر است. لئونارد میتواند قبل از آخرین A
حرف C
و بعد از آن حرفهای CA
را اضافه کند و در مجموع ۳ واحد هزینه میکند.
در این مثال هزینهی اضافه کردن A
و C
برابر با ۱۰ و هزینهی اضافه کردن G
و T
برابر با ۱۵ است. لئونارد میتواند قبل از دومین G
حرف T
و بعد از آن حرف C
را اضافه کند و به رشتهی TCGCTGCAG
برسد که TGCAG
را به عنوان زیر رشته دارد و در مجموع ۲۵ واحد هزینه میکند.