牛客练习赛134 —— B题 python 补题 + 题解

牛客练习赛134 B

题目描述

在这里插入图片描述

示例输入：

示例输出：

在这里插入图片描述

解题思路：

题目大意

给定一个2行n列的矩阵，允许交换两列一次，从左上角(1,1)走到右下角(2,n)，每一步只能向右或向下移动，求经过元素的最大和。

核心思路: 往下走只有一次，所以选择枚举往下走的分界点

路径结构分析
路径必然在第一行右走若干列后下到第二行继续右走。设转折点为i（在第i列下移），路径和为第一行前i列的和 + 第二行i到n列的和。
不交换列的情况
预处理第一行的前缀和sum1和第二行的后缀和sum2，遍历所有i，计算sum1[i]+sum2[i]的最大值。
交换列的增益计算
通过预处理四个数组，分三种情况计算交换后的最大增益：
- Case1：交换左半区某列与右半区某列，最大化差值之和。
- Case2：交换左半区某列与当前列，提升当前列的第二行值。
- Case3：交换右半区某列与当前列，提升当前列的第一行值。
边界处理
单独处理i=1和i=n的情况，分别考虑与右侧或左侧列交换的增益。

实现步骤

预处理前缀和与后缀和
- sum1[i]：第一行前i列的和。
- sum2[i]：第二行i到n列的和。
预处理最大值与差值数组
- max1[i]：i到n列第一行的最大值。
- max2[i]：前i列第二行的最大值。
- diff1[i]：i到n列（第一行-第二行）的最大差值。
- diff2[i]：前i列（第二行-第一行）的最大差值。
分情况计算最大路径和
- 遍历中间转折点，计算三种交换情况的增益。
- 单独处理首尾列的交换增益。

实现code：

t = int(input())
for _ in range(t):n = int(input())a1 = list(map(int, input().split()))a2 = list(map(int, input().split()))ans = -float('inf')if n == 1:  # 特判print(a1[0] + a2[0])continue# 第一行的前缀和：sum1[i]表示前i列第一行的元素和sum1 = [0] * (n + 1)for i in range(1, n + 1):sum1[i] = sum1[i - 1] + a1[i - 1]# 第二行的后缀和：sum2[i]表示从第i列到第n列第二行的元素和sum2 = [0] * (n + 2)for i in range(n, 0, -1):sum2[i] = sum2[i + 1] + a2[i - 1]# 枚举所有可能的分界点i，路径为:前i列走第一行，第i列到第n列走第二行for i in range(1, n + 1):ans = max(ans, sum1[i] + sum2[i])  # 不交换列的情况'''预处理max1,max2和diff1,diff2数组：max1[i]:第i列到第n列第一行的最大值max2[i]:前i列中第二行的最大值diff1[i]:第i列到第n列中（第一行元素 - 第二行元素）的最大差值diff2[i]:前i列中（第二行元素 - 第一行元素）的最大差值'''max1 = [-float('inf')] * (n + 2)diff1 = [-float('inf')] * (n + 2)for i in range(n, 0, -1):max1[i] = max(max1[i + 1], a1[i - 1])diff1[i] = max(diff1[i + 1], a1[i - 1] - a2[i - 1])max2 = [-float('inf')] * (n + 1)diff2 = [-float('inf')] * (n + 1)for i in range(1, n + 1):max2[i] = max(max2[i - 1], a2[i - 1])diff2[i] = max(diff2[i - 1], a2[i - 1] - a1[i - 1])# 交换列for i in range(2, n):# Case1：交换i左边某列和右边某列:找到最大的左边差值与右边差值之和case1 = sum1[i] + sum2[i] + diff2[i - 1] + diff1[i + 1]# Case2：交换i左边某列与当前列:当前列的第二行被替换为左边更大的值case2 = sum1[i] + sum2[i] - a2[i - 1] + max2[i - 1]# Case3：交换i右边某列与当前列:当前列的第一行被替换为右边更大的值case3 = sum1[i] + sum2[i] - a1[i - 1] + max1[i + 1]ans = max(ans, case1, case2, case3)# 特判：转折点为第一列,最后一列if n >= 2:# Case4：交换第一列与右边某列：第一列的第一行被替换为右边更大的值case4 = sum1[1] + sum2[1] - a1[0] + max1[2]# Case5：交换最后一列与左边某列：最后一列的第二行被替换为左边更大的值case5 = sum1[n] + sum2[n] - a2[n - 1] + max2[n - 1]ans = max(ans, case4, case5)print(ans)