当前位置:   article > 正文

OD C卷 - 分披萨_分披萨od

分披萨od

分披萨

  • 有大小不同的奇数块披萨;
  • 从A开始轮流取披萨,第一块可以任意选取,其他都必须从缺口开始选;
  • B每次都选最大块的, A知道B的想法(A不一定要取最大的,只求最终块数和最多);
  • 求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 有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)


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/1001891
推荐阅读
相关标签
  

闽ICP备14008679号