SWERC12

RNA Secondary Structure (Problem D)

Online Judge: [1]

RNA หรือ Ribonucleic Acid เป็นโครงสร้างพื้นฐานของโมเลกุล ซึ่งประกอบด้วยสายโซ่ของส่วนประกอบที่เรียกว่า nucleotides โดย nucleotide นั้นมีอยู่ 4 แบบ เรียกว่าฐาน ซึ่งเขียนแทนด้วยตัวอักษา A, C, G หรือ U โครงสร้างหลักของ RNA นั้นประกอบด้วยฐานดังกล่าวนี้ เราจะกล่าวถึงโครงสร้างรองของ RNA ซึ่งก็คือการจับคู่ของฐานต่าง ๆ โดยที่ฐาน A สามารถจับคู่ได้กับฐาน U และ ฐาน C จับคู่กับฐาน G ความเสถียรของ RNA นั้นขึ้นอยู่กับจำนวนคู่ฐานที่จับกันได้ โครงสร้างสุดท้ายของ RNA คือ โครงสร้างที่มีการจับคู่มากที่สุด

กำหนดให้โครงสร้างหลักนั้นถูกอธิบายด้วยสายอักขระ ของตัวอักษร ACGU กฎของโครงสร้างของโครงสร้างรองเป็นดังต่อไปนี้

1. ฐาน A ใด ๆ สามารถจับกับฐาน U ได้
2. ฐาน C ใด ๆ สามารถจับกับฐาน G ได้
3. ฐานแต่ละฐานนั้นสามารถจับคู่ได้เพียงคู่เดียว
4. กำหนดให้ w < x และ y < z และ w < y ถ้าฐานซึ่งอยู่ ณ ตำแหน่ง w จับคู่กับ ฐาน ณ ตำแหน่ง x และ ฐาน ณ ตำแหน่ง y จับคู่กับฐาน ณ ตำแหน่ง z แล้ว เงื่อนใขหนึ่งในสองข้อต่อไปนี้จะต้องเป็นจริง
   1. y > x
   2. z < x
   3. การจับคู่ระหว่าง C กับ G นั้นไม่สามารถมีได้เกิน K คู่

คุณจะได้รับสายอักขระที่อธิบายถึงโครงสร้างหลักของสิ่งมีชีวิตชนิดหนึ่ง หน้าที่ของคุณคือคำนวณจำนวนการจับคู่ในโครงสร้างสุดท้ายที่ตรงกับเงื่อนไขข้างต้นนี้

โครงสร้างหลักที่มีให้นั้นจะอยู่ในรูปแบบ Run Length Encoding ซึ่งอักขระที่เหมือนกันที่อยู่ติดกันนั้นจะถูกลดรูปเป็นอักขระตามด้วยตัวเลขที่บอกจำนวนตัวที่อยู่ติดกัน ตัวอย่างเช่น “AAAACCGAAUUG” สามารถเขียนได้เป็น “A4C2G1A2U2G1” กล่าวโดยละเอียดคือโครงสร้างหลักนั้นจะอยู่ในรูปแบบ $<c_{1}f_{1}c_{2}f_{2}c_{3}f_{3}...c_{n}f_{n}>$ โดยที่ $c_{i}$ จะเป็น A, C, G หรือ U และ $f_{i}$ จะเป็นตัวเลขจำนวนเต็มบวก

นอกจากนี้ เรายังทราบว่าสิ่งมีชีวิตที่เรากำลังศึกษาอยู่นั้นมีลักษณะดังต่อไปนี้

1. $f_{1}+f_{2}+f_{3}+...f_{n}<=10050$
2. $f_{1}<=5000$
3. $f_{n}<=5000$
4. $f_{2}+f_{3}+f_{4}+...+f_{n-1}<=50$

ข้อมูลนำเข้า

บรรทัดแรกมีค่า T <= 200 ซึ่งระบุจำนวน Test Case ทั้งหมด โดยแต่ละ Test Case เป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วย run length encoding ของ RNA
• บรรทัดที่สองประกอบด้วยค่า K (0 <= K <= 20) ซึ่งระบุจำนวนคู่ C-G มากสุดที่สามารถมีได้

ข้อมูลส่งออก

ในแต่ละ Test Case ให้พิมพ์หมายเลขของ Test Case ตามด้วยจำนวนการจับคู่มากสุดที่สามารถทำได้

ตัวอย่างและภาพประกอบ

ให้ดูจาก http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3992