@makarworld

Сложный шифр

Для передачи сообщения по открытому каналу связи шифровальщики придумали сложный шифр. Шифр состоит из N различных чисел, записанных в одну строку через пробелы. Дешифрованное сообщение состоит из K чисел, которые являются номерами исходных чисел, разбивающих исходное сообщение на K частей (подпоследовательностей), так что сумма минимумов каждой подпоследовательности будет максимальна.

Итак, от Вас требуется написать программу, которая выполняет дешифровку заданного шифра.

Формат ввода
Первая строка входного файла содержит два разделенных пробелом натуральных числа N и К (1 ≤ K < N ≤ 300).

Вторая строка входного файла содержит зашифрованное сообщение –N разделенных пробелом целых различных натуральных чисел а1, а2, а3… аn (1 ≤ ai ≤ 10).

Формат вывода
Выходной файл в первой строке содержит максимальную сумму К слагаемых, которые являются минимумами каждой части разбиения последовательности на K частей.

Во второй строке выходного файла содержится дешифрованное сообщение из разделенных пробелом К натуральных чисел – номеров чисел в последовательности, которые завершают каждую из подпоследовательностей зашифрованного сообщения.

Пример
Ввод
10 5
1 10 2 8 9 3 5 4 7 6
Вывод
27
3 4 5 8 10

0

@eaa

makarworld, что конкретно не получается?

0

@mr-Crocodile

eaa, если не сложно, поясни, что в этой задаче вообще происходит?!
что такое Это что означает?


я не тупой, но туплю конкретно, извини!

0

@eaa

Массив [1, 10, 2, 8, 9, 3, 5, 4, 7, 6] нужно разбить на ровно k подмассивов чтобы выполнялось условие.

Двумерное ДП, рекурсия, восстановление ответа.

1

@mr-Crocodile

eaa, спасибо за ответ!

вот сразу полегчало, не поверишь...

не, чуток и правда стало яснее. нужно массив из 10 чисел разбить ровно на 5 подмассивов (т.е. по 2 числа в массиве), так, чтобы "сумма минимумов каждой подпоследовательности будет максимальна"
но не скажу, чтобы я теперь смог эту задачу решить, но хотя бы смог понять, что требуется. это уже неплохо!

0

@eaa

не по два числа, а минимум 1 число должно быть.
например:
[1, 10, 2], [8], [9], [3, 5, 4], [7, 6]

1

@mr-Crocodile

о как. теперь всё окончательно (про само задание) понятно, большое спасибо!
вижу, что порядок нельзя менять, т.е. нельзя разбить так
[1,2,3,4,5] [10] [8] [9] [6,7] =>сумма минимумов = 34

0