Разбор задачи "C. Тир"

Во-первых, нужно сказать, что в данной задаче элементы теории вероятностей не играют существенной роли. То есть можно считать, что у i-ой мишени всего лишь есть некоторый "вес", который равен как раз вероятности попадания в нее, а именно p_i. Достаточно просто понять, почему это так:

Математическое ожидание количества попадания в i-ую мишень равно M_i = 0 * (1 - p_i) + 1 * p_i = p_i, а математическое ожидание попадания в несколько мишеней по очереди равно сумме математических ожиданий, а значит, по уже сказанному, равно сумме вероятностей попадания в эти мишени.

Поэтому нами (авторами этой задачи) предлагается решение динамическим программированием, а именно:

D_i равно максимальному математическому ожиданию попаданий, если у нас на данный момент прицел направлен в мишень номер i, причем, текущее время (которое, однако, не является параметром и явно нигде не учитывается) меньше или равно t_i.

Тогда D_i = p_i + max(D_j), где j-ая мишень обозначает следующую мишешь, куда мы переместим прицел. Соответственно, для нее должно выполняться условие: t_i + dist(i, j) ≤ t_j, для того, чтобы такой переход имел место быть. Очевидно, что граф переходов ацикличен, а это значит, что такое решение верно.

Ответом является максимальное D_i по всем 1 ≤ i ≤ n. Асимптотика данного решение O(n²).