题面描述

在一个包含两行和m列的糖果迷宫中，小A和小B从左上角出发，目标是到达右下角。小A在路径中尽量减少小B可以获得的糖果，而小B希望在小A走完后能尽可能多地吃到糖果。通过动态规划的方法，我们可以计算出小B最多能够吃掉的糖果数量。具体实现时，首先记录小A的路径及其获得的糖果，然后基于小A的路径计算小B的最大糖果数，最终得出小B可以获得的最大糖果总数。

题目分析

我们需要计算小A和小B分别在迷宫中移动时所能吃到的糖果数量。小A从左上角开始，向右或向下移动，直到到达终点。小B则从小A结束的地方开始，从终点位置返回到左上角，但不能吃小A吃过的糖果。小A的目标是尽量减少小B吃掉的糖果，而小B希望在小A走完后能吃到尽可能多的糖果。

思路

1. 前缀和的计算：

   • 我们需要计算小A和小B在每一列之前吃掉的糖果和。通过前缀和数组，我们能够快速获得任意区间内的糖果总数。
   • 对于每一行，建立一个前缀和数组qzs，其中qzs[i][j]表示第i行前j列的糖果总和。这样可以方便地计算出小A和小B在任意分割点之前和之后的糖果数量。

2. 分割点的选择：

   • 小A从左上角出发到达某个分割点，然后停止，接着小B从该分割点开始向右走至终点。在这个过程中，我们需要考虑每一个可能的分割点。
   • 对于每一个分割点i，小A在分割点之前的总糖果数为qzs[0][i + 1]（第一行的前缀和），而小B在该分割点之后的糖果数则为qzs[1][m] - qzs[1][i]（第二行的前缀和减去分割点的糖果）。

3. 最小化最大值：

   • 对于每个分割点，计算小A在分割点之前和小B在分割点之后所能吃到的糖果数量。我们需要找出小B可能吃到的最大糖果数，并对所有分割点的结果取最小值。这样可以确保小A所吃的糖果数量最小化时，小B所能获得的糖果数量最大。

4. 代码实现：

   • 代码中首先读取糖果迷宫的数据，计算前缀和，然后遍历每一个可能的分割点，计算相应的糖果数量，最后输出小B能够吃到的最大糖果数。

时间复杂度

整个算法的时间复杂度为 (O(m))，因为我们只需遍历一次二维数组来计算前缀和，另外一次遍历进行计算，整体为线性复杂度。

代码实现

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m;
    cin >> m;
    
    // 初始化糖果迷宫和前缀和数组
    vector<vector<int>> grid(2, vector<int>(m));
    vector<vector<int>> qzs(2, vector<int>(m + 1));
    
    // 读取第一行糖果并计算前缀和
    for (int j = 0; j < m; j++) {
        cin >> grid[0][j];
        qzs[0][j + 1] = qzs[0][j] + grid[0][j];
    }
    
    // 读取第二行糖果并计算前缀和
    for (int j = 0; j < m; j++) {
        cin >> grid[1][j];
        qzs[1][j + 1] = qzs[1][j] + grid[1][j];
    }
    
    // 初始化最小糖果损失值为较大数
    long long ans = INT_MAX;
    
    // 遍历每个分割点，从0到m-1
    for (int i = 0; i < m; i++) {
        // 计算小B在该分割点的最大可能值
        int tmp = max(qzs[1][i], qzs[0][m] - qzs[0][i + 1]);
        // 更新答案，取最小值
        ans = min(ans, static_cast<long long>(tmp));
    }
    
    // 输出小B最多能吃到的糖果数量
    cout << ans << endl;
    
    return 0;
}

Python 代码

# 输入迷宫的列数
m = int(input())
# 读取糖果分布并初始化前缀和数组
grid = [list(map(int, input().split())) for _ in range(2)]

# 初始化前缀和数组
qzs = [[0] * (m + 1) for _ in range(2)]
for j in range(m):
    # 计算第一行前缀和
    qzs[0][j + 1] = qzs[0][j] + grid[0][j]
    # 计算第二行前缀和
    qzs[1][j + 1] = qzs[1][j] + grid[1][j]

# 设定答案为一个较大的值
ans = float('inf')
# 遍历所有分割点，找到最优分割
for i in range(1, m + 1):
    # 计算小B在当前分割点的最优结果
    tmp = max(qzs[1][i - 1], qzs[0][m] - qzs[0][i])
    # 更新最优解
    ans = min(ans, tmp)

# 输出小B最多可以吃到的糖果数
print(ans)

Java 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        
        // 初始化糖果迷宫和前缀和数组
        int[][] grid = new int[2][m];
        int[][] qzs = new int[2][m + 1];
        
        // 读取第一行糖果并计算前缀和
        for (int j = 0; j < m; j++) {
            grid[0][j] = sc.nextInt();
            qzs[0][j + 1] = qzs[0][j] + grid[0][j];
        }
        
        // 读取第二行糖果并计算前缀和
        for (int j = 0; j < m; j++) {
            grid[1][j] = sc.nextInt();
            qzs[1][j + 1] = qzs[1][j] + grid[1][j];
        }

        // 初始化最小糖果损失值为较大数
        long ans = Integer.MAX_VALUE;
        
        // 遍历每个分割点，从0到m-1
        for (int i = 0; i < m; i++) {
            // 计算小B在该分割点的最大可能值
            int tmp = Math.max(qzs[1][i], qzs[0][m] - qzs[0][i + 1]);
            // 更新答案，取最小值
            ans = Math.min(ans, tmp);
        }

        // 输出小B最多能吃到的糖果数量
        System.out.println(ans);
    }
}

代码注释总结

• 前缀和数组：qzs[0][j+1] 记录小A在迷宫第0行的糖果和，qzs[1][j+1] 记录小B在迷宫第1行的糖果和。
• 分割点循环：遍历每一个可能的分割点，通过比较小B和小A的前缀和，计算当前点的最小损失值。
• 更新和输出：在遍历完所有列后，输出小B的最大糖果数量。

题目描述

小明有一个神奇的糖果迷宫，这个迷宫是一个矩形迷宫，包含了两行（行数为2）和m列（列数为m）的格子。每个格子中都有不同的分数，由二维数组a[i][j]表示，其中i表示行号，j表示列号。

小A和小B从迷宫的左上角（位置a[0][0]）出发，走到迷宫的右下角（位置a[1][m-1]）。在这个过程中，他只能进行向右或向下的移动，每到达一个格子，他们都会吃掉这个格子的糖果。

假设小A先走，他会获得吃掉路径中的糖果，然后小B开始走，他不能重复吃掉小A吃过的糖果。

小A的目标是要尽量减少小B吃掉的糖果总数，而小B则希望在小A走完后，自己能吃掉更多的糖果总数。

请你计算小B最多可以吃掉多少糖果。

输入格式

第一行一个整数 m，表示迷宫的列数。

接下来两行，每行 m 个整数，表示当前位置的糖果数。

输出格式

输出小B最多可以吃掉的糖果数。

4
1 5 2 7
5 3 4 1

8

说明

$1 \le m \le 10^5$