网格游戏 图解题解

两行网格里的机器人博弈，到底在求什么

grid 是 2 行 n 列，每格写着点数。两个机器人先后从左上角 (0,0) 走到右下角 (1,n-1)，每步只能向右或向下。机器人一先走，收走沿途点数、把格子清零；机器人二再走，收走剩下的。机器人一想让机器人二拿得尽量少，机器人二想让自己拿得尽量多，两边都最优，问机器人二拿多少。题面上排是 3、1、2、5，下排是 4、2、1、2，答案 6。

两边都要最优，是不是得把走法两两配对推演

两个机器人各自求最优，乍看像要把机器人一走法和机器人二应对两两摆到一起推演，组合一多就压不住。路径其实没几种：只能向右或向下，任何一条从 (0,0) 到 (1,n-1) 的路都长一个样——上排往右走到某一列，在那列往下拐进下排，再沿下排走到底。机器人一真正能决定的，只有在哪一列下拐，一共就 n 种选择。

拐点一定下来，机器人二只够得着两块残料

机器人一沿某列下拐、清零整条路后，没被碰过的只剩两块：上排拐点右边的一段，和下排拐点左边的一段。机器人二同样只能向右向下走，一旦下拐就回不到上排，这两块没法都要，只能挑点数大的一块。

于是机器人二在这一列能拿到的，就是 max(上排拐点右段之和, 下排拐点左段之和)。前者是从拐点右边加到头的后缀和，后者是从最左加到拐点左边的前缀和——前缀和、后缀和，就是从头、从尾累加起来的跑动总和。机器人一要做的，是在所有拐点里让较大者尽量小，逐列取最小。

用一前一后两个滚动和，一趟就扫完

不必每列都把两段重新加一遍。参考代码里 s1 先存上排整行的和，s2 从 0 起。从左往右枚举拐点列时，先让 s1 减掉上排当前这个数，s1 就变成上排后缀和；此刻 s2 恰好是下排前缀和；拿 max(s1, s2) 更新答案后，再把 s2 加上下排当前这个数，留给下一列。一列只做减、比、加各一次，走完就是 O(n)。

拿题面的 3、1、2、5 和 4、2、1、2 逐列走一遍

上排总和 11 先当作 s1,s2 从 0 起。拐第 0 列：s1 减 3 变 8,s2 还是 0，较大者 8，答案记 8;s2 加 4 变 4。拐第 1 列：s1 减 1 变 7,s2 是 4，较大者 7，答案更新成 7;s2 加 2 变 6。

拐第 2 列：s1 减 2 变 5,s2 是 6，较大者取 6，答案更新成 6;s2 加 1 变 7。拐第 3 列：s1 减 5 变 0,s2 是 7，较大者 7，不比 6 小，答案仍是 6。四列下来，机器人一拐第 2 列把对手压到 6，即最终答案。

别把拐点列算进残料，也别用 int 接总和

复杂度先交代：求一次上排和是 O(n)，枚举 n 个拐点每列常数步，时间 O(n)，只用几个滚动变量，空间 O(1)。剩下几处提前避开。拐点那一列上下两格都被机器人一收走，上排后缀从它右边一列起、下排前缀到它左边一列止，归错边就多算一格。点数总和能到五十亿、越过 int 上限，C 加加 用 long long、Java 用 long,int 会溢出成负数。n 为 1 时上下都没有残料，机器人二只能拿 0。最容易想歪的，是把机器人二所得当成两块之和——路径不能回头，较大者才是它真拿到的。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        ans = inf
        s1, s2 = sum(grid[0]), 0
        for j, v in enumerate(grid[0]):
            s1 -= v
            ans = min(ans, max(s1, s2))
            s2 += grid[1][j]
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;

class Solution {
public:
    long long gridGame(vector<vector<int>>& grid) {
        ll ans = LLONG_MAX;
        int n = grid[0].size();
        ll s1 = 0, s2 = 0;
        for (int& v : grid[0]) s1 += v;
        for (int j = 0; j < n; ++j) {
            s1 -= grid[0][j];
            ans = min(ans, max(s1, s2));
            s2 += grid[1][j];
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public long gridGame(int[][] grid) {
        long ans = Long.MAX_VALUE;
        long s1 = 0, s2 = 0;
        for (int v : grid[0]) {
            s1 += v;
        }
        int n = grid[0].length;
        for (int j = 0; j < n; ++j) {
            s1 -= grid[0][j];
            ans = Math.min(ans, Math.max(s1, s2));
            s2 += grid[1][j];
        }
        return ans;
    }
}