赞
踩
示例1
输入:
5
8
2
10
5
7
输出:
19
说明:
A拿10
B拿5
A拿7
B拿8
A拿2
此时A拿到最多19
示例2:
输入:
7
4
3
8
2
10
9
20
输出:
35
示例3
输入:
23
45
78
21
12
14
52
76
123
302
34
43
73
37
89
98
101
102
201
120
24
15
17
28
输出:
1032
思路:
A先随意取一块,有n种取法,0 1 2… n-1
A取的当前索引i
开始 A 有n种取法,A取的当前索引i对应的值 + 回溯值,若大于result,则更新result;
# 输入总块数
n = int(input().strip())
# 每块的大小 - 列表
nums = []
for i in range(n):
nums.append(int(input().strip()))
# A取的时候,矩阵对应[left, right]位置保存A可以获取的最大和
matrix = [[0 for i in range(n)] for j in range(n)]
# 回溯函数
def backtrace(left, right):
# 全局变量
global n, nums, matrix
# B取
if nums[left] > nums[right]:
left = (left + n + 1) % n
elif nums[left] < nums[right]: # 块的大小各不相同
right = (right + n - 1) % n # 右边的指针向左走一步
# A 取并 给matrix赋值(matrix对应位置未赋值时)
if matrix[left][right] <= 0: # 为初始值
if left == right: # 结束
matrix[left][right] = nums[left]
else:
new_left = (left + 1) % n # 左边指针向右走一步
new_right = (right + n - 1) % n
# B取过后,A也取较大的
# A从左边追溯
matrix[left][right] = nums[left] + backtrace(new_left, right)
# A从右边追溯,取较大者
if nums[right] + backtrace(left, new_right) > matrix[left][right]:
matrix[left][right] = nums[right] + backtrace(left, new_right)
return matrix[left][right]
else:
return matrix[left][right]
result = 0 # 记录最大结果
i = 0 # n种情况 0 1 2 ... n-1
while True:
if i >= n:
break
else:
left = (i + n + 1) % n
right = (i + n - 1) % n
other_sum = backtrace(left, right)
if other_sum + nums[i] > result:
result = other_sum + nums[i]
i += 1
print(result)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。