最后的算法舞

问题描述

[上一个相关问题:一种具有复杂性的舞蹈]

故事:我将以特定顺序参加舞蹈比赛，播放 n 首歌.不过，我无法跳舞每一首歌，因为我需要在每次舞蹈前做好准备，而在之后需要休息. (幸运的是，一个舞蹈的休息时间可能与下一舞蹈的准备时间重叠.)

The story: I'm about to take part in a dance contest with n songs in a specific order. I can't dance to every single song, though, because I need time to prepare before each dance, and time to rest afterward. (Fortunately, the rest time from one dance can overlap with the preparation time for the next.)

我知道我跳舞的每首歌能得到多少分，我想最大化我的总分.

I know what score I can get for each song I do dance to, and I want to maximize my total score.

所以，我有三个数组:

• 得分( i )是我跳舞## em> i 歌曲可获得的分数.
• prep ( i )是我必须在歌曲# i 之前立即跳过的歌曲数，否则我做不到歌曲# i . (例如，如果 prep (4)  =  2，那么除非我跳过了#2和#3，否则我将无法跳舞到#4.)
• rest ( i )是我在歌曲# i 之后必须立即跳过的歌曲数，如果我做了## em > i . (例如，如果 rest (4)  =  2，而我跳到#4歌曲，那么我就必须同时跳过#5和#6.)

• score(i) is the score I can get for dancing to song #i.
• prep(i) is the number of songs I have to skip immediately before song #i, or else I can't do song #i. (For example, if prep(4) = 2, then I can't dance to song #4 unless I've skipped both song #2 and song #3.)
• rest(i) is the number of songs I have to skip immediately after song #i, if I did song #i. (For example, if rest(4) = 2, and I dance to song #4, then I have to skip both song #5 and song #6.)

准备( i )或休息( i )都没有超出上限，将其称为 M .

Neither prep(i) nor rest(i) ever exceeds an upper bound, call it M.

如何最大化我的分数?它的复杂性是什么?

How can I maximize my score? What's its complexity?

我的尝试:

根据已经给出的答案，

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

并在此基础上进行构建，以便使我们有一个类似的死时间:

and build on it, so that we have as a dead time something like:

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

但是我很担心，因为正如我的链接问题中所述，i应该下降.有人可以帮忙吗?这种重叠使我感到困惑.

but I am worried, since i should descend, as mentioned in my linked question. Can anybody help please? That overlapping confuses me.

推荐答案

# 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)))
             )

在这种情况下，我正在考虑三种可能性:

In this case, I am thinking of three possibilities:

• 跳过当前歌曲-> Opt(i+1)
• 跳舞到当前歌曲-> Score(i)和
  • 等待ith歌曲或
  的静止期
  • 等待提供足够准备时间的第一首歌曲-> myPrep(i)
  • Skips current song -> Opt(i+1)
  • Dances to current song -> Score(i) and
    • waits for the resting period of ith song or
    • waits for the first song which provides enough prep time -> myPrep(i)

    我和我自己辩论是否应该在ith之后包含所有准备时间足够的可能的歌曲，但后来认为Opt(myPrep(i))应该获得正确的编号，因此我们不需要在之后包含所有歌曲myPrep(i)计算ith首歌曲

    I debated with myself if I should include all the possible songs that have enough prep time after ith but then thought the Opt(myPrep(i)) should get the right number and hence we don't need to include all of the songs after myPrep(i) in calculation of ith song

    这篇关于最后的算法舞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！