NALP's blog

By NALP, 10 years ago, In Russian

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


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

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

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

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

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

Ответом является максимальное Di по всем 1 ≤ i ≤ n. Асимптотика данного решение O(n2).
 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it