Олимпиадные задачи. Динамическое программирование

Сентябрь 7, 2022

Главная
Алгебра
Олимпиадные задачи. Динамическое программирование

Содержание

2. Задача «Таблица»
4. Первый способ
5. Второй способ С диагоналями. Нужен, чтобы хранить не 3 строки одной таблицы (B), а по две
6. L R B Что должно получиться Первую строку заполняем первой строкой из А Заполняем вторую строку
7. L R B Что должно получиться Первую строку заполняем первой строкой из А Заполняем вторую строку
8. L R B Что должно получиться Теперь можно и третью строку В заполнить B[i, j] =
9. L R B Что должно получиться B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1] L[i, j]
10. L R B Что должно получиться B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1] L[i, j]
11. L R B Что должно получиться B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1] L[i, j]
12. L R B Что должно получиться Теперь можно и третью строку В заполнить B[i, j] =
13. L R B Что должно получиться Далее заполняем по формулам третьи строки L и R B[i,
14. L R B Что должно получиться Далее заполняем по формулам третьи строки L и R и
16. Скачать презентацию

Слайд 2

Задача «Таблица»

Слайд 3

Слайд 4

Первый способ

Слайд 5

Второй способ
С диагоналями. Нужен, чтобы хранить не 3 строки одной таблицы

(B), а по две строки трех таблиц (L, R, B)

Слайд 6

L
R
B
Что должно
получиться
Первую строку заполняем первой строкой из А
Заполняем вторую строку

B по-честному

Слайд 7

L
R
B
Что должно
получиться
Первую строку заполняем первой строкой из А
Заполняем вторую строку

B по-честному

Слайд 8

L
R
B
Что должно
получиться
Теперь можно и третью строку В заполнить
B[i, j] =

2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Заполняем вторую строку L и R по формулам

Слайд 9

L
R
B
Что должно
получиться
B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j]

= L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Теперь можно и третью строку В заполнить

Слайд 10

L
R
B
Что должно
получиться
B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j]

= L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Теперь можно и третью строку В заполнить

Слайд 11

L
R
B
Что должно
получиться
B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j]

= L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Теперь можно и третью строку В заполнить

Слайд 12

L
R
B
Что должно
получиться
Теперь можно и третью строку В заполнить
B[i, j] =

2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Слайд 13

L
R
B
Что должно
получиться
Далее заполняем по формулам третьи строки L и R
B[i,

j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]

Слайд 14

L
R
B
Что должно
получиться
Далее заполняем по формулам третьи строки L и R

и т.д.

B[i, j] = 2*B[i-1,j] + L[i-1,j-1] + R[i+1,j+1]
L[i, j] = L[i-1,j-1] + B[i,j]
R[i, j] = R[i-1,j+1] + B[i,j]