Fişierul intrare/ieşire:game.in, game.outSursăConcurs Shumen juniori 2017
AutorAutor NecunoscutAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Game

Boyan se joacă un joc pe calculator. La început există N bile aşezate în linie. Pe fiecare bilă este scris un număr şi pe oricare două bile vecine sunt numere diferite. Jocul are următorii paşi:

1. Jucătorul şterge o bilă dintre cele date.
2. Cât timp există bile consecutive cu acelaşi număr, acestea sunt automat şterse din linie.
3. Dacă mai rămân bile, se merge la pasul 1, altfel jocul se termină.

Scorul este numărul total de bile şterse automat. Scopul este să se maximizeze scorul.

Să considerăm un exemplu cu 6 bile, numerotate {1, 2, 3, 2, 1, 5}.
1. Boyan şterge bila cu numărul 3.
Bilele rămare sunt: {1, 2, 2, 1, 5}.
2. Ştergând bilele vecine pe care este scrisă aceeaşi valoare, avem:
{1, 2, 2, 1, 5} -> {1, 1, 5} -> 5.
Bila rămasă este 5.
3. Mai rămân bile, deci se merge la pasul 1.

1. Boyan şterge bila cu numărul 5.
Bilele rămase: {}.
2. Nu sunt bile vecine pe care este scris acela şi număr.
3. Nu mai sunt bile rămase, deci se termină jocul.

Numărul de bile şterse automat este 4.
Acesta este scorul maxim posibil pentru acest joc.
Boyan este un jucător bun, dar nu este sigur că joacă mereu optim.
Scrieţi un program care să îl ajute să obţină cel mai mare scor posibil.

Date de intrare

Fişierul de intrare game.in conţine pe prima linie un întreg pozitiv N.
Pe a doua linie conţine N întregi pozitivi reprezentând numerele scrise pe bile.

Date de ieşire

În fişierul de ieşire game.out se va afişa scorul maxim pe care Boyan îl poate obţine.

Restricţii

  • 1 ≤ N ≤ 500
  • 1 ≤ numărul scris pe o bilă ≤ 1 000 000
  • În 20% dintre teste N ≤ 10
  • În 50% dintre teste N ≤ 100

Exemplu

game.ingame.out
6
1 2 3 2 1 5
4
9
1 5 1 3 2 4 2 3 1
6

Explicaţie

În al doilea exemplu se şterg bilele de pe poziţiile: 2, 6 şi 9.

Trebuie sa te autentifici pentru a trimite solutii. Click aici