Изменения

Перейти к: навигация, поиск

Динамическое программирование по профилю

6 байт добавлено, 15:18, 21 марта 2018
Пример
Профилем будет пара <tex>(p, i)</tex>, в <tex>p</tex> будет информация о <tex>n + 1</tex> маленьком квадратике слева от базовой линии, имеющем с ней общие точки; <tex>i</tex> обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер <tex>i + 1</tex>. Горизонтали будем нумеровать с нуля, так что <tex>i</tex> пробегает значения от <tex>0</tex> до <tex>n - 1</tex>.
Пусть <tex>d[ipr_1][jpr_2] = 1</tex> если из профиля <tex>pr_1</tex> = <tex>(p_1, i_1)</tex> можно перейти в <tex>pr_2 = (p_2, i_2)</tex>, иначе <tex>0</tex>.
* Eсли <tex>i < n - 1</tex>, то <tex>i_1 + 1 = i_2</tex>, иначе <tex>i_2 = 0 </tex>;
Анонимный участник

Навигация