Со вчерашнего дня накинулся на тему динамического программирования. По сути вся задача сводится к определению состояния, атомарных(базовых) величин и построению рекурентной формулы. Решая простые примеры, казалось, что все понятно. Однако столкнувшись с олимпиадными задачами, очень сложно выявить возможность декомпозировать задачу на подзадачи.

Вот, например, задача 1409F из архива codeforces. В строке нужно изменить определенное количество символов, для того, чтобы слово из 2-х букв было бы подпоследовательностью как можно большее количество раз. В качестве состояний не понятно, что взять. Думал, например, взять количество подпоследовательностей в строке длины n-1. Но это состояние не имеет смысла из-за того, что количество перестановок ограниченное число. Как решить эту задачу, я пока не имею представления.

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

Начинаю вести блог для документирования результатов подготовки к олимпиаде по спортивному программированию. Срок подготовки очень маленький промежуток времени, поэтому буду стараться интенсивно нарешивать задачи. Часть обширных тем я делегировал на моего коллегу по команде. Я решил усиленно подготовиться к следующим темам: - Динамическое Программирование (дп) - Жадные алгоритмы - Длинная арифметика - Сортировка Срок подготовки 5 дней по 2 задачи уровня не меньше 1300 по данным темам.