我遇到了一个问题，说你可以唤醒一个睡着的人，这个人的状态从代表睡眠的S变为代表清醒的.。
当你叫醒一个人时，旁边的人也会从睡梦中醒来，因为距离很近。例如，有三个人睡在一个房间里如果你叫醒中间的人，那么这三个人都会醒来，也就是说SSS变成...。
但是，如果你叫醒了一个已经醒了的人，那么他的状态不会改变但是他旁边的人会醒着的，也就是说S.S变成...，
问题是，如果房间里有熟睡的人和清醒的人。在唤醒人们之后，这个房间里醒着的人最多是多少？。
一个棘手的例子是s=S和.=k。
醒着的人，房间就会变小
醒着的人，房间就会变小
也就是说，你可以在唤醒persons和personS.SSSS之后让这个房间里的每个人都清醒因此，这个例子的答案将是k人而不是2。
我用python编写了我的解决方案，列出了我能叫醒的所有人的索引组合叫醒他们，数醒的人数。
它只适用于短字符串和少数人。
我想我需要在算法层面上做些改进。任何建议或暗示都将不胜感激。
提前谢谢。
import sys
import itertools
memo = {}
def wake(s, i):
if i in memo:
return memo[i]
s = list(s)
for n in i:
if n == 0:
s[n], s[n+1] = '.', '.'
elif n == len(s)-1:
s[n-1], s[n] = '.', '.'
else:
s[n-1], s[n], s[n+1] = '.', '.', '.'
memo[i] = s.count('.')
return memo[i]
if __name__ == '__main__':
with open(sys.argv[1]) as f:
line = f.readline()
n, k = map(int, list(line.rstrip().split(' ')))
line = f.readline()
s = line.rstrip()
ans = 0
for i in itertools.combinations(range(n), k):
temp = wake(s, i)
if temp > ans:
ans = temp
print(ans)
为了测试的目的，我会放一些测试用例和下面的正确答案。
Format:
n k
s
ans
5 3
.....
5
12 2
.SSSS.SS.SSS
9
7 1
..S.SS.
6
67 4
SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S
48
29 2
.S.....SSSSS.SSSS...SS.SSS.SS
18
79 6
.S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.
47
41 9
.S.S...S.S.....S.SS.SS.SS.SS.S.SS.SS.....
41
91 67
...SS.SS....S...S.S.SS...SSS.SSSSSSS.....SS..S.S.SS...S..S..S.SS.......SSSSS.S.S...S.SS.S.S
91
7 97
SSSS.SS
7
276 23
SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.
100
最佳答案
让dp[n][k]成为我们醒来的'S'人数，如果我们与n第一个人打交道并且已经醒来的k人。对于dp[n][k]我想没有理由叫醒人数n，因为没有人可以叫醒我们（因为我们只与n+1第一人打交道），所以最好叫醒人数n并且也叫醒人数n-1。我后来用的逻辑。
然后，如果我们有动作，我们可以叫醒所有的人。如果我们没有行动，那么答案就是已经清醒的人数。
如果n：
如果n <= 3，那么n，因为我们没有叫醒任何人。
如果k > 0，则n > 3。这里我们处理了2个案例：如果我们唤醒了某人，然后是第三人称，然后我们就失去了1个移动，所以我们计算了我们刚刚睡醒的人的数量，并检查了其他人的最大数量。如果我们没有叫醒任何人，那么我们就有第个人，如果他的初始状态和我们仍然有移动。所以这个问题的答案是k = 0。
答案是：dp[n][k] = dp[n][0] = 0只处理睡着的人数，但我们唤醒了他们。所以，为了得到完整的答案，我们只需加上已经醒着的人数。
ans = 0
if n <= 3:
if k > 0:
ans = n
else:
ans = s.count('.')
else:
dp = [[0 for x in range(k + 1)] for y in range(n)]
dp[2][1] = s[:3].count('S')
for i in range(3, n):
t = s[i - 3 : i].count('S')
for j in range(1, k + 1):
dp[i][j] = max(dp[i - 3][j - 1] + t, dp[i - 1][j])
for i in range(2, n):
ans = max(ans, dp[i][k])
ans += s.count('.')
print(ans)