Олимпиадный тренинг

Задача . F. Пары карт


Задача

Темы: реализация дп жадные алгоритмы хэши *3000

Есть колода из \(n\) карт, каждая из которых имеет один из \(k\) типов. Вам дана последовательность \(a_1, a_2, \dots, a_n\), обозначающая типы карт в колоде сверху вниз. И \(n\), и \(k\) — четные числа.

Вы играете с этими картами. Сначала вы берете \(k\) верхних карт из колоды. Затем происходит следующее на каждом ходу игры:

  • вы выбираете ровно две карты из вашей руки и играете их. Если у этих карт одинаковый тип, вы зарабатываете монету;
  • затем, если колода не пуста, вы берете ровно две верхние карты из нее;
  • затем, если и ваша рука, и ваша колода пусты, игра заканчивается. В противном случае начинается новый ход.

Вам нужно посчитать максимальное количество монет, которое вы можете заработать во время игры.

Входные данные

Первая строка содержит два целых числа \(n\) и \(k\) (\(2 \le k \le n \le 1000\), оба \(n\) и \(k\) — четные).

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le k\)).

Выходные данные

Выведите одно целое число — максимальное количество монет, которое вы можете заработать.


Примеры
№Входные данныеВыходные данные
1 
4 2
1 2 1 2
 
0
2 
8 2
2 1 2 2 1 2 1 2
 
1
3 
4 4
1 2 1 2
 
2
4 
6 4
3 2 3 1 2 1
 
3
5 
6 4
3 2 3 3 2 1
 
2
6 
18 6
5 6 1 1 6 5 4 1 5 1 1 6 2 6 2 2 6 3
 
6
7 
8 4
1 2 3 4 4 3 1 2
 
2
8 
8 4
1 2 3 4 4 3 3 2
 
3

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++4
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет