OD C卷 - 分披萨

分披萨

有大小不同的奇数块披萨；
从A开始轮流取披萨，第一块可以任意选取，其他都必须从缺口开始选；
B每次都选最大块的， A知道B的想法；
求A能获得的披萨块总和的最大值；
输入描述：
第一行输入n(奇数，表示披萨块数)， [3, 500)
接下来的n行，每行输入一个披萨块的大小
输出描述：
A能获得的披萨块总和的最大值；

示例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
- left = (i + 1 + n) % n;
- right = (i -1 + n) % n;
- backtrace(left, right)，先B取一个较大的，然后A取并赋值matrix[left][right]，其中matrix是一个n*n的矩阵，初始化为0；
- matrix[left][right] = max(A先取左边的值 + 回溯结果，A先取右边的值+回溯结果)，并返回
- left == right 时，matrix[left][right] 赋值并返回
- 针对示例1 更新后的matrix为:
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)