D. Давашгүй даалгавар

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Одоо дэлгүүрт маш удаан хүлээгдсэн тоглоом болох Колдер Скрүүлс V: Нводск иржээ. Уг тоглоом нь маш хүнд тоглоом болж таарсан бөгөөд ихэнх сурагчид хамгийн сүүлийн даалгаврыг биелүүлж чадахгүй байв (Уг даалгаврын нэр нь "We don't go to Nvodsk..." байв). Энэ нь бүр өвлийн шалгалтад хүртэл нөлөөлжээ. Захирал өвлийн шалгалтыг 4-р сар хүртэл хойшлуулах талаар хүртэл бодож үзсэн бөгөөд учир нь тэрээр уг даалгаврыг өөрийн биеэр биелүүлэхийг хүсэж байв. Гэвч гэнэтхэн түүний оффис-ийн үүдэнд нэгэн танихгүй хүн ирсэн ба тэрээр "Өдрийн мэнд. Намайг Чак гэдэг би ямар ч даалгаврыг биелүүлж чадна" хэмээн хэлжээ.

Одоо тэд тал талд суун тоглоомыг тоглож байгаа бөгөөд уг даалгаврыг биелүүлж чадахгүй л байв. Гол асуудал нь хамгийн сүүлийн босс-ыг устгахын тулд та заавал захиануудыг эмхлэх урлагийн онцгой чадвартай болохоо батлан харуулах хэрэгтэй ажээ. Гэвч та үүнийг хийхийн тулд заавал жинхэнэ шидтэн байх хэрэгтэй юм. Гэхдээ та шидтэн-үүд өрсөлдөж эхлэхээр юу болдог талаар төсөөлж үзсэн үү?

Уг бодлогыг илүү албан ёсоор тайлбарлая: танд нэгэн тэмдэгт мөр болон бүхэл тоо $a_{i}$-уудын нэгэн олонлог өгөгдөв. Та палиндром байх дурын нэгэн дэд тэмдэгт мөрийг сонгох ба үүнийг устгаж болох байв. Ингэх явцад та $a_{k}$-тай тэнцүү хэмжээний оноо хожих бөгөөд энд $k$ нь устгагдсан палиндром-ын урттай тэнцүү байх юм. Зарим $k$-ын хувьд $a_{k} =$ -1 байх бөгөөд энэ нь таны устгасан палиндром-ын урттай тэмдэгт мөрүүд нь хориотой болохыг илэрхийлэх ажээ. Ямар нэгэн дэд тэмдэгт мөрийг устгасны дараагаар үлдсэн хэсгүүдийг шууд хооронд нь нийлүүлэх ба өөрөөр хэлбэл хугацааны ямар ч мөчид тэмдэгт мөр нь хоосон зай агуулаагүй байх юм. Тэмдэгт мөр дотор дор хаяж нэг ширхэг устгаж болох дэд тэмдэгт мөр байгаа тохиолдолд уг үйлдлийг давтан хийсээр байна. Эцэст бүх оноонуудыг нэмэх юм.

Тэгвэл нийлбэр онооны хамгийн их утгыг тодорхойлно уу.

"Өө" хэмээн Чак хэлээд өөрийн сууж байсан сандлаасаа босонгоо -- "Би палиндром устгах дуртай байсан л даа, яг л чам шиг, гэвч нэг өдөр би өвдөгнөөсөө сум сугалан авсан юм даа" гэж хэлжээ.

Оролт

Эхний мөрөнд бүхэл тоо $l$ ($1 ≤ l ≤ 150$) өгөгдөх ба энэ нь тэмдэгт мөрийн уртыг илэрхийлнэ.

2-дахь мөрөнд яг $l$ ширхэг бүхэл тоонууд $a_{k}$ ($ - 1 ≤ a_{k} ≤ 10^{5}$)-ууд өгөгдөх ба эдгээр нь палиндром устгахад тоглогчийн хожих оноонуудыг илэрхийлнэ.

3-дахь мөрөнд яг $l$ ширхэг Латин жижиг үсгүүд өгөгдөх ба эдгээр нь тоглогч палиндром-уудыг устгаж болох анхны тэмдэгт мөрийг илэрхийлэх юм.

Уг мөрөнд өөр ямар нэгэн зүйл өгөгдөөгүй байна.

Гаралт

Хэрэв та өгөгдсөн тэмдэгт мөр дээр тогловол хожиж болох хамгийн их онооны тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
7
-1 -1 -1 -1 -1 -1 -1
abacaba
Гаралт
0
Оролт
7
1 -1 -1 -1 -1 -1 -1
abacaba
Гаралт
7
Оролт
7
1 5 -1 -1 -1 -1 10
abacaba
Гаралт
16

Тэмдэглэл

Эхний жишээнд бид ямар ч дэд тэмдэгт мөрийг устгаж чадахгүй бөгөөд иймд хожиж болох хамгийн их оноо нь $0$ байх юм. 2-дахь жишээнд бид зөвхөн урт нь $1$-тэй тэнцүү байх палиндром-уудыг устгаж болох бөгөөд ингэснээр хэрэв бид бүх тэмдэгт мөрийг тэр чигт нь устгавал $7$ оноо хожиж чадна. 3-дахь жишээнд оновчтой стратеги нь дараах байдалтай байна: эхлээд бид $c$ гэсэн тэмдэгтийг устгах ба дараа нь $aa$-г үүний дараа $bb$-г тэгээд эцэст нь $aa$-г устгах юм. Ингэснээр бид $1 + 3 * 5 = 16$ оноо хожиж чадах ажээ.

Сэтгэгдлүүдийг ачааллаж байна...