По каналу связи передаётся последовательность натуральных чисел — показания прибора. В течение $N$ минут ($N$ — натуральное число) прибор ежеминутно регистрирует значение напряжения в электрической…
- 1
Нумеруем показания последовательности начиная с единицы. Для трёх выбранных позиций $i<j<l$ должны выполняться условия $j-i\geq K$ и $l-j\geq K$.
- 2
Для каждой позиции поддерживаем максимальное произведение пары чисел, выбранных среди уже доступных позиций с необходимым расстоянием. При обработке очередного числа учитываем только позиции, отстоящие от него минимум на $K$.
Ещё 2 шага — в полном решении
По каналу связи передаётся последовательность натуральных чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения в электрической сети и передаёт его на…
- 1
Пронумеруем показания от $1$ до $N$. Если выбран элемент на позиции $i$, следующий выбранный элемент может находиться только на позиции не ранее $i+K$.
- 2
Будем поддерживать лучшие произведения для выбора одного, двух и трёх допустимых показаний среди обработанных позиций.
Ещё 3 шага — в полном решении
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на $k = 109$ и при этом…
- 1
Перебор всех вариантов выбора одного числа из каждой тройки имеет экспоненциальную сложность, поэтому для файла B он непригоден.
- 2
Состояние динамического программирования определяется остатком текущей суммы по модулю $109$. Для каждого остатка сохраняется максимальная достижимая сумма.
Ещё 3 шага — в полном решении
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S_i$, $S_j$, $S_k$ три элемента последовательности $S$, где $i < j < k$. Определите в…
- 1
Преобразуем выражение:$$(S_i-S_j)+(S_k-S_j)=S_i+S_k-2S_j$$
- 2
При фиксированном среднем индексе $j$ выгоднее всего выбрать максимальный элемент среди элементов с индексами меньше $j$ и максимальный элемент среди элементов с индексами больше $j$.
Ещё 3 шага — в полном решении
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S_i$, $S_j$, $S_k$ три элемента последовательности $S$, где $i < j < k$. Определите в…
- 1
Преобразуем выражение:$$(S_i-S_j)+(S_k-S_j)=S_i+S_k-2S_j$$
- 2
При фиксированном среднем индексе $j$ выгодно выбрать максимальный элемент слева от него и максимальный элемент справа от него.$$F_j=\max_{i<j}S_i+\max_{k>j}S_k-2S_j$$
Ещё 2 шага — в полном решении
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с…
- 1
Обозначим через $P_i$ сумму первых $i$ элементов последовательности, причём $P_0 = 0$. Тогда сумма элементов на отрезке $[L;M]$ равна $P_M-P_{L-1}$, а сумма элементов на отрезке $[M+1;R]$ равна $P_R-P_M$.$$D=(P_R-P_M)-(P_M-P_{L-1})=P_R-2P_M+P_{L-1}$$
- 2
Для каждого правого конца $R$ необходимо найти минимум величины $2P_M-P_{L-1}$ среди всех допустимых пар $L<M<R-1$. При увеличении $R$ в множество допустимых пар добавляется новая пара с $M=R-2$ и всеми допустимыми $L<M$.$$D_R=P_R-\min(2P_M-P_{L-1})$$
Ещё 2 шага — в полном решении
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на $k = 109$ и при этом…
- 1
Состояние динамического программирования определяется остатком текущей суммы при делении на $109$. Для каждого остатка сохраняется наибольшая возможная сумма.$$dp[r] = \text{максимальная сумма с остатком } r$$
- 2
При обработке очередной тройки перебираем только три варианта выбора. Для каждого прежнего остатка $r$ и числа $x$ из тройки обновляем состояние с новым остатком.$$new[(r+x) \bmod 109] = \max(new[(r+x) \bmod 109],\, dp[r]+x)$$
Ещё 2 шага — в полном решении
Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна $N$ километров. Нулевой и $N$-й километры трассы…
- 1
Пусть пункты пронумерованы от $0$ до $N-1$, а в пункте $i$ находится $a_i$ комплектов. Если цех расположен в пункте $k$, расстояние до пункта $i$ равно $\min(|i-k|, N-|i-k|)$.
- 2
Стоимость положения $k$ равна $F(k)=\sum_{i=0}^{N-1} a_i\min(|i-k|,N-|i-k|)$. Прямой перебор всех пар имеет сложность $O(N^2)$ и не подходит для файла B.
Ещё 3 шага — в полном решении
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с…
- 1
Обозначим префиксную сумму через $P_i=a_1+a_2+\dots+a_i$, причём $P_0=0$. Сумма подпоследовательности $S(L,R)$ равна $P_R-P_{L-1}$.
- 2
Сумма $P_R-P_{L-1}$ чётна тогда и только тогда, когда $P_R$ и $P_{L-1}$ имеют одинаковую чётность.
Ещё 2 шага — в полном решении
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с…
- 1
Введём префиксные суммы $P_0=0$, $P_i=a_1+a_2+\dots+a_i$. Сумма подпоследовательности от $j+1$ до $i$ равна разности $P_i-P_j$.$$S(j+1,i)=P_i-P_j$$
- 2
Разность $P_i-P_j$ нечётна тогда и только тогда, когда префиксные суммы имеют разную чётность.
Ещё 3 шага — в полном решении
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S_i$, $S_j$, $S_k$ три элемента последовательности $S$, где $i < j < k$. Определите в…
- 1
Для фиксированного среднего индекса $j$ выражение можно преобразовать:$$(S_j-S_i)+(S_j-S_k)=2S_j-S_i-S_k$$
- 2
При фиксированном $j$ для максимизации выражения необходимо выбрать минимальный элемент слева от позиции $j$ и минимальный элемент справа от позиции $j$.
Ещё 3 шага — в полном решении
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с…
- 1
Обозначим через $P_i$ сумму первых $i$ элементов последовательности. Тогда сумма $S(L, M)$ равна $P_M - P_{L-1}$, а сумма $S(M+1, R)$ равна $P_R - P_M$.$$D = (P_M - P_{L-1}) - (P_R - P_M) = 2P_M - P_{L-1} - P_R$$
- 2
Для каждого разделителя $M$ требуется выбрать минимальное значение $P_{L-1}$ среди индексов $0 \leq L-1 < M$ и минимальное значение $P_R$ среди индексов $M+2 \leq R \leq N$.
Ещё 2 шага — в полном решении