具有复杂性的舞蹈 [英] A dance with an aglorithm's complexity

问题描述

我即将参加舞蹈比赛，明天是最重要的一天！我知道竞赛的n歌曲及其顺序的列表.经过大量的探索，我能够很好地确定裁判和我的技能，以至于如果我跳到列表中的第i首歌曲，即score(i).

I am about to take part in a dance contest and tomorrow is the big day! I know apriori the list with the n songs of the contest and their order. After much scouting, I was able to determine the judges and my skills so good that I can accurately predict my result if I dance the i-th song of the list, i.e. score(i).

但是，在第i首歌曲之后，我需要休息时间，即我无法跳舞下一首rest(i)首歌曲，即歌曲i + 1，...，i + rest(i).我可以跳舞的歌曲数量没有其他限制.给出一种有效的算法来计算理想的最大总分及其复杂性.

However, after the i-th song, I need time to rest, namely I cannot dance the next rest(i) songs, i.e. songs i + 1, ..., i + rest(i). No other constraint exists for the number of songs I can dance. Give an effective algorithm for computing your ideally maximum total score and its complexity.

因此，我认为应该使用递归，在max(i) = max(i + 1)或max(i) = score(i) + max(i + 1 + rest(i))的位置，然后在每一步中从这两个中选出最好的一个.有人可以帮忙吗?

So I think that recursion should be used, where max(i) = max(i + 1) or max(i) = score(i) + max(i + 1 + rest(i)) and then pick the best out of this two at every step. Can someone help?

推荐答案

让n首歌曲索引为0..n-1.假设Opt(i)是我们从歌曲i开始自由跳舞的最高总分. Opt的重复发生次数是

Let there be n songs indexed 0..n-1. Let Opt(i) be the maximum total score given that we're free to dance starting on song i. The recurrence for Opt is

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

直觉上，我们要么不跳舞i歌曲，获取剩余时间的价值，要么我们对歌曲i进行评分，休息，然后获取休息后的时间的价值.

Intuitively, we either don't dance song i and get the value of the remaining time, or we do, score song i, rest, and get the value of the time after resting.

应该以i递减的方式评估此重复发生，并将先前计算的值缓存在数组中.运行时间为O(n).

This recurrence should be evaluated for i descending, with the previously calculated values cached in an array. The running time is O(n).

这篇关于具有复杂性的舞蹈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！