题目描述
一个字符串,从某个点开始扩张,同时从边界以相同的速度开始缩短,要使得剩下的部分得分最高。
思路
1.不论以什么方法,最后剩下的字符串长度固定,为N/2向上取整。
所以要求的其实是字符串当中得分最高的已知长度的连续子串。
2.使用前缀和求解每个子串的得分,并获得最大值。
*.证明或找到一种策略,使得求解的最大值保证能够被取到。
时间复杂度
1.计算目标子串的长度,复杂度O(1)。
2.计算前缀和,复杂度O(N),并利用前缀和求最高分子串,复杂度O(N)。
达到最大值的策略
子串长度>=母串长度/2。所以在字串中,必然存在一个点,它到目标子串边界的距离不小于母串边界。
以那个点作为生成子串的起始点,即作画的第一幅画的点。
此后每次母串某一端缩短,则将子串向那一侧扩张一个字符。即某侧墙面被摧毁,就在靠近那一侧的墙面作画。
如此,子串边界到目标子串边界的距离将仍然不小于母串边界。
重复这个过程,即可达到目标子串。
PS.我反正是凭借直觉先做完,然后再考虑能不能达到的问题的。
python3 代码
T = int(input())
for C in range(T):
n = int(input())
a = input()
S = [0]*(n+1)
result_len = int((n+1)/2)
for i in range(len(a)):
S[i+1] = int(a[i])+S[i]
result_score = 0
for i in range(len(a)-result_len+1):
result_score = max(result_score, S[i+result_len]-S[i])
print("Case #%d: %d"%(C+1, result_score))