562. 壁画【Python实现】
Date:3.1
Key:前缀和
思路
一个简单的思维转换吧,可以把问题看成:先手的人从任意位置上开始选数且下次选数必须和之前选过的数位置上相邻;后手的人只能从两端开始选数且下次选数必须和之前选过的数位置上相邻或者选择另一端的端点;每个位置上的数字只能被选一次;双方都是最优选择的情况下,要求先手能够选到的最大的和
直接说结论:任意一个长度为$\frac{n+1}{2}$的区间都是合法区间,故只需要长度为$\frac{n+1}{2}$的区间中选择元素和最大的区间即可
简单证明:
将区间可进行一次划分,类似于:xxooo|ooxx或者xxoo|ooxx,只会产生两种情况:1.左右两侧的x的数量和o的数量相同 2.一侧x的数量比o的数量多1,另一侧两者数量是相同的 显然第2种情况相比于第1种情况是更坏的情况,能够证明情况2能达到则情况1一定也能达到,因为先手的优势,可以优先选择占掉一个中心位置且靠数量不等的一侧,在上面的例子中也就是第5个位置,如此可以回到情况1,然后每次根据x选择的位置,选择和其同侧能够选择到的位置即可,这样进行操作能够保证所有的选择是可达的
实现上就很简单了,只需要处理出前缀和数组,在枚举一个端点遍历一遍即可出答案
代码
t = int(input())
for _ in range(t):
n = int(input())
s = '!' + input()
dp = [0] * (n+1)
for i in range(1, n+1):
dp[i] = dp[i-1] + ord(s[i]) - 48
ans = 0
for i in range(1, n+1):
j = i + (n+1) // 2 - 1
if j > n:
break
ans = max(ans, dp[j]-dp[i-1])
print('Case #%d: %d' %(_+1, ans))