Последнего алгоритмического танец

Question

[Предыдущий связанный с этим вопрос: A dance with an aglorithm's complexity]

История: Я собираюсь принять участие в танцевальном конкурсе с п песен в определенном порядке. Я не могу танцевать каждую песню, потому что мне нужно время, чтобы подготовиться перед каждым танцем, и время отдыха после этого. (К счастью, время отдыха от одного танца может перекрываться со временем подготовки к следующему.)

Я знаю, какой счет я могу получить за каждую песню I do танцуйте, и я хочу максимизировать свой общий балл.

Итак, у меня есть три массива:

• забить (я) является оценкой я могу получить для танцев на песню # я.
• приготовительный (я) это количество песен, которые я должен немедленно пропустить перед песней # я, иначе я не могу сделать песню # я. (Например, если преп (4)   =   2, то я не могу танцевать под песню # 4 если я не пропустил как песня # 2 и # 3 песни.)
• отдыха (я) - это количество песен, которые я должен пропустить сразу после песни # i, если бы я сделал песню # i. (Например, если остальное (4)   =   2, и я танцую на песню # 4, то я должен пропустить как песня # 5 и песня # 6.)

Ни преп (i) а также отдых (i) когда-либо превышает верхнюю границу, назовите его M.

Как я могу увеличить свой балл? В чем его сложность?

---

Моей попытка:

На основании ответа уже дали, считать, что

Opt(i) = max(Opt(i+1), 
      Score(i) + Opt(i + 1 + rest(i))) for i = 0..n-1. 

и построить на нем, так что у нас есть, как мертвое время что-то вроде:

Opt(i + 1 + max(prep(i), rest(i))) 

, но я волнуюсь, так как i должен сойти, как упоминалось в моем связанном вопросе. Может ли кто-нибудь помочь, пожалуйста? Это совпадение меня смущает.

Answer 1

# Get the first song that can be danced to assuming he danced to `i` and wanted to wait till prep time of a song 
def myPrep(i): 
    for j in range(i+1,n): 
     if j - prep(j) > i: 
      return j 

for i in range(0,n-1): 
    Opt(i) = max(Opt(i+1), 
       (Score(i) + Opt(i + 1 + rest(i))), 
       (Score(i) + Opt(i + 1 + myPrep(i))) 
      ) 

В данном случае я имею в виду три возможности:

• Пропускает текущую песню ->Opt(i+1)
• Dances к текущей песне ->Score(i) и
  • ждет покоящихся период ith песня или
  • ждет первой песни, которая предоставляет eno тьфу время приготовительный ->myPrep(i)

я спорил с собой, если я должен включать в себя все возможные песни, которые имеют достаточно времени на подготовку после ith но потом подумал Opt(myPrep(i)) должен получить правильное число и, следовательно, мы не делаем нужно включить все песни после myPrep(i) в расчете ith песня