2003 : Miners
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 16 megabyte(s)
กลุ่มของคนขุดถ่านหินทำงานที่เหมืองสองเหมือง การขุดถ่านหินเป็นงานที่ยากลำบาก ทำให้คนขุดถ่านหินต้องการอาหารที่ทำให้ทนทำงานอยู่ได้ เมื่อมีการส่งอาหารมาที่เหมือง คนขุดถ่านหินจะขุดถ่านหินได้จำนวนหนึ่ง ในการส่งอาหารแต่ละเที่ยว ประเภทอาหารที่ส่งอาจจะเป็น เนื้อ ปลา หรือขนมปัง

คนขุดถ่านหินชอบความหลากหลายของอาหารที่รับประทาน ซึ่งทำให้พวกเขาจะมีประสิทธิภาพในการทำงานถ้าอาหารที่ส่งมามีความแตกต่างกัน กล่าวคือเมื่อพวกเขาได้รับการส่งอาหารแต่ละเที่ยว พวกเขาจะพิจารณาการส่งอาหารที่เพิ่งได้รับและการส่งอาหารก่อนหน้านั้นสองเที่ยวล่าสุด (หรือน้อยกว่านั้นถ้าจำนวนเที่ยวยังไม่ถึง) และจะทำงานดังนี้:
  • ถ้าทุกเที่ยวการส่งอาหาร มีอาหารประเภทเดียว พวกเขาจะขุดถ่านหินได้หนึ่งหน่วย
  • ถ้าในการส่งอาหารดังกล่าวมีอาหารสองประเภทในการส่งอาหารเที่ยวเหล่านั้น พวกเขาจะขุดถ่านหินได้สองหน่วย
  • ถ้ามีประเภทอาหารสามประเภท พวกเขาจะขุดถ่านหินได้สามหน่วย
เราทราบล่วงหน้าถึงลำดับและชนิดของอาหารในการส่งอาหารแต่ละเที่ยว จึงเป็นไปได้ว่าเราจะสามารถปรับเปลี่ยนปริมาณถ่านหินที่ขุดได้ทั้งหมดได้ โดยการเลือกว่าการส่งอาหารแต่ละเที่ยวจะส่งไปยังเหมืองใดเหมืองหนึ่ง ทั้งนี้ เหมืองทั้งสองไม่จำเป็นต้องได้รับอาหารในจำนวนเที่ยวที่เท่ากัน (ที่จริงแล้ว การส่งทุกเที่ยวจะส่งไปยังเหมืองเดียวกันทั้งหมดก็ได้)

โจทย์
โปรแกรมของคุณจะได้รับรายการของประเภทอาหารตามลำดับที่จะต้องส่งไปยังเหมืองใดเหมืองหนึ่ง จงเขียนโปรแกรมเพื่อคำนวณปริมาณรวมของถ่านหินที่จะขุดได้มากที่สุด (largest total amount of coal) ที่สามารถทำได้จากการควบคุมการส่งอาหารว่าการส่งอาหารเที่ยวใดไปยังเหมือง 1 และเที่ยวใดไปยังเหมือง 2

ข้อมูลนำเข้า
บรรทัดแรก ของข้อมูลป้อนเข้าจะมีจำนวนเต็ม N (1 ≤ N ≤ 100 000) แทนจำนวนเที่ยวของการส่งอาหาร
บรรทัดที่สอง จะมีสตริงที่ประกอบด้วยอักขระ N ตัว แทนรายการของประเภทอาหาร เรียงลำดับตามเที่ยวที่จะต้องส่งไปยังเหมือง แต่ละตัวอักขระจะเป็นตัวพิมพ์ใหญ่ โดยที่ ‘M’ แทนเนื้อ ‘F’ แทนปลา และ ‘B’ แทนขนมปัง

ข้อมูลส่งออก
ข้อมูลส่งออกประกอบด้วยจำนวนเต็มหนึ่งจำนวน ระบุปริมาณถ่านหินมากที่สุดที่สามารถขุดได้

ที่มา: International Olympiad in Informatics 2007 DAY 2
ZAGREB – CROATIA AUGUST 15 – 22
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
6
MBMFFB		 12
16
MMBMBBBBMMMMMBMB		 29

ความช่วยเหลือ: Hint[1]  Hint[2]  Hint[3]  

กำลังออนไลน์: 30 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)