Минимальная сумма показаний
По каналу связи передаётся последовательность целых чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение силы тока и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ минут, а сумма этих трёх чисел была минимально возможной. Даны два входных файла: файл A и файл B. В каждом файле в первой строке содержится натуральное число $K$, во второй — количество показаний $N$ ($1 \leqslant N \leqslant 10\,000\,000$, $N>K$), а далее записаны $N$ натуральных чисел, не превышающих $10\,000\,000$. Запишите два числа: сначала искомую величину для файла A, затем для файла B. Типовой пример имеет иллюстративный характер; для выполнения задания используются данные из прилагаемых файлов. Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
1Мягкая — с чего смотретьдеңгей 1 из 3
Как хранить минимальные суммы для выбора одного, двух и трёх показаний, если выбранные позиции должны находиться на расстоянии не менее $K$?
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Для каждого нового показания поддерживайте минимум среди подходящих предыдущих состояний: для двух чисел — минимум одного числа не позднее позиции $i-K$, для трёх — минимум суммы двух чисел не позднее позиции $i-K$.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
При последовательной обработке вычисляйте $d_1(i)=a_i$, $d_2(i)=a_i+\min d_1(j)$ и $d_3(i)=a_i+\min d_2(j)$ для $j\leq i-K$. Ответом является минимум всех значений $d_3(i)$.