棋

GitHub跳转原题关系图返回列表

三连判定只看相邻 3 列，把每列压成 3bit 图案加 3bit 已计入标记，做 3 列滑窗的带状状压 DP。

启发题

启发记录： 第一次接触延迟推定计算的状态压缩

OJ: roj

题目 ID: 20024

难度:提高

标签:状态压缩动态规划

创建: 2026-08-29 00:08

更新: 2026-10-07 10:45

RBook 文章:
状态压缩 DP

目录

  1. 形式化题目
  2. 思路
    1. 状态转移方程
    2. DP 转移表格
  3. 代码
  4. 复杂度
  5. 另一种解法：五列窗口（不记账）
    1. 思路
    2. dp 里到底存了什么
    3. 代码
    4. 复杂度
  6. 总结

形式化题目

给定一个 3×n3\times n 的棋盘，每个格子可以填 X 或 O。格子被染色：

  • 格子是 X，且它位于连续三个 X 排成的一线里（同行、同列或两条对角线）→ 染红；
  • 格子是 O，且它位于连续三个 O 排成的一线里 → 染蓝；
  • 否则染黑。

每个格子有权值 ai,ja_{i,j}（可以为负），分数 == 所有红格权值之和 −- 所有蓝格权值之和。求染色方案的最大分数，n⩽103n\leqslant 10^3。

思路

一句话本质：三连判定只看相邻 3 列，所以把每列压成 3bit 图案 + 3bit "已计入"标记，做 3 列滑窗的窄带状压 DP，让每个格子的权值在它滑出窗口时恰好结算一次。

问题？ 直接枚举棋盘染色有多少种方案？

每种方案 23n2^{3n} 种，n=1000n=1000 时完全不可行，但它是"按题意直接判定、绝不会错"的基准。先看这个暴力，它把 3n3n 个格子拉平成一条 01 选择序列，生成完整棋盘后在叶子统一判定每个格子是否位于三连里：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:42
 * update_at: 2026-08-28 23:42
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// 把 3*n 个格子按"行优先"拉平成一条 01 序列：choose[k] = 1 表示画 X，0 表示画 O。
// 递归只负责生成完整序列，到叶子节点再统一按题意判定每个格子是否位于三连里，
// 计算分数（红 + 蓝 -）取最大值。只能跑 n <= 4（2^(3n) 种棋盘）。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 5;          // 暴力只处理 n <= 4
const ll NEG_INF = -(1LL << 60);

int n;
ll w[3][MAXN];               // w[行][列]：权值
int choose[3 * MAXN];        // choose[k]：第 k 个格子画什么，1 = X，0 = O
ll ans;

// 判断格子 (r,c) 是否位于"连续三个和它相同"的一线里
// 方向 4 种：横(0,1)、纵(1,0)、对角线 ↘(1,1)、对角线 ↗(1,-1)
// 对每个方向，三连中心相对 (r,c) 的偏移 m 只可能是 -1、0、1
bool in_triple(int r, int c) {
    int sym = choose[r * n + c];
    int dr[4] = {0, 1, 1, 1};
    int dc[4] = {1, 0, 1, -1};
    for (int d = 0; d < 4; d++) {
        for (int m = -1; m <= 1; m++) {
            bool ok = true;
            for (int t = -1; t <= 1; t++) {
                int rr = r + (m + t) * dr[d];
                int cc = c + (m + t) * dc[d];
                if (rr < 0 || rr >= 3 || cc < 0 || cc >= n) { ok = false; break; }
                if (choose[rr * n + cc] != sym) { ok = false; break; }
            }
            if (ok) return true;
        }
    }
    return false;
}

// 统计完整棋盘的分数：红格权值和 - 蓝格权值和，黑色格子不贡献
ll calc_answer() {
    ll sum = 0;
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < n; c++) {
            if (!in_triple(r, c)) continue;            // 黑色
            int sgn = choose[r * n + c] ? 1 : -1;      // X 红 +，O 蓝 -
            sum += w[r][c] * sgn;
        }
    }
    return sum;
}

void dfs(int dep) {
    if (dep == 3 * n) {                                // 一条完整 01 序列生成完毕
        ll val = calc_answer();
        if (ans < val) ans = val;
        return;
    }
    // 这一层枚举第 dep 个格子的选择：0 = O，1 = X
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    if (n > 4) { // 超出暴力适用范围，防止越界
        cerr << "brute.cpp 仅支持 n <= 4\n";
        return 0;
    }
    for (int r = 0; r < 3; r++)
        for (int c = 0; c < n; c++)
            cin >> w[r][c];

    ans = NEG_INF;
    dfs(0);
    cout << ans << '\n';
    return 0;
}

问题？ 一个格子是红/蓝/黑，到底由哪些格子决定？

"连续三个相同"的线只有 4 类：横（同行相邻 3 列）、纵（同列相邻 3 行）、对角线 ↘ 和 ↗（各跨相邻 3 列）。所以判定格子 (r,c)(r,c) 只需要看它自己、同列上下两格、左右两列同行格和两条对角线的斜邻格——也就是以它为中心、半径 2 的邻域。

问题？ 从"每个格子看邻居"出发，从左往右扫描时状态要记多少列？

格子 (r,c)(r,c) 的横/斜三连可以跨到 c+2c+2 列，看起来要记未来两列的信息，非常臃肿。这里换个角度：把"决定颜色"推迟到"所有相关三连都可见"时再做。包含列 cc 的横/斜三连，最右边只到列 c+2c+2；因此当窗口恰好覆盖 [c,c+1,c+2][c, c+1, c+2] 三列时，列 cc 中每个格子是否红/蓝已经完全确定，可以一次性结算整列（纵向三连在列内，也在这时判定）。这就是关键卡点①：三连判定只需要相邻 3 列的信息，列状态只要 3bit。状态充分性：更早的列已全部结算完毕，不再影响未来任何判定，所以只需记录最近两列。

注意 n⩽2n \leqslant 2 需要特判：列数不足 3 时（n⩽2n \leqslant 2）不存在横向/对角线三连，只有纵向三连，代码用 solve_small 单独处理；n=1n=1 时主流程状态里"旧列"不存在，必须特判，否则收尾访问越界。

问题？ 一个格子可能同时属于多个三连（例如全 X 时一个格子横、纵、两条对角线全是三连），贡献怎么保证只算一次？

每个三连被"发现"时如果都去加权，同一个格子会被重复计权。解决方法是给每列额外维护 3bit colored 标记：格子第一次被判定为红/蓝时打上标记并计入权值，之后再被其它三连命中时直接跳过。这就是关键卡点②。有了标记，权值结算就只发生在"该格子所在的列滑出窗口左端"这一次。

问题？ 状态具体记什么？

处理到第 ii 列（尚未放置）时，状态记录最近两列——列 i−2i-2（窗口左列 AA）与列 i−1i-1（中列 BB）的图案（3bit）+ colored 标记（3bit），共 12bit；下一轮放置列 ii（新列 CC）形成 3 列窗口，并让列 i−2i-2 滑出结算。状态数 212=40962^{12}=4096。转移时枚举新列图案(8 种),在 3 列窗口里判定 4 类三连:

  • 纵向：旧列整列图案为 000 或 111；
  • 横向：三列同一行图案相同；
  • 对角线 ↘：格 (0,旧)(1,中)(2,新)(0,旧)(1,中)(2,新) 相同；
  • 对角线 ↗：格 (2,旧)(1,中)(0,新)(2,旧)(1,中)(0,新) 相同。

旧列格子命中 → 结算权值（红 ++、蓝 −-）；中列、新列格子命中 → 只打 colored 标记，等它们成为旧列时再结算。

问题？ 一个 3×33\times 3 窗口里有 8 条直线，为什么只判定 6 条？

3×33\times 3 内长度为 3 的直线共 8 条：3 横、3 竖、2 对角。但窗口 (A,B,C)(A,B,C) 这一轮只判定"最左格落在 A 列"的直线：

  • 3 条横向、2 条对角线的最左格都在 A 列 → 全部收录；
  • 3 条纵向里只有 A 列整列落在窗口内 → 收录 1 条；B 列、C 列的纵向三连要各自等它们变成窗口左列 A 时才判定（下一轮、下下轮）。

展开就是下面这 6 条：

text
1 条纵向： (0,A)(1,A)(2,A)
3 条横向： (0,A)(0,B)(0,C)   (1,A)(1,B)(1,C)   (2,A)(2,B)(2,C)
2 条对角： (0,A)(1,B)(2,C)   (2,A)(1,B)(0,C)

所以判定的是 1+3+2=61+3+2=6 条而不是 8 条。这样安排的意义在于：每条三连在整个 DP 中恰好被检查一次，正好对应“每条三连都在它最左列滑到窗口左端时结算”，也解释了为什么结算函数只需要处理旧列 A 的账。代码里把这 6 条三连直接写成常量表 T[6][3]：T[t][k] 是第 tt 条三连的第 kk 个格子，用结构体 offset{row, col} 记录“第几行 + 哪一列（0=A, 1=B, 2=C）”，gain() 用一个循环统一判定，不必为每类三连单独写代码。

问题？ 这 12bit 状态是“想”出来的一大坨吗？脑容量不够怎么办？

不是。它只是几个小积木的乘积：2 列 ×（每列 3bit 图案 + 3bit 标记）× 3 行 = 12bit。真正撑爆脑子的不是位数，而是“当场给格子定色”的直觉；把目标换成“让下一列能算对”，状态就是被逼出来的，不用靠记忆堆。

问题？ 为什么“当场定色”一定会失败？

一条三连跨 3 列，一个格子会被好几个窗口反复命中。在窗口 (c−1,c,c+1)(c-1,c,c+1) 就给 (r,c)(r,c) 加权，等窗口 (c,c+1,c+2)(c,c+1,c+2) 再次命中它时会重复加；当场不加，等它滑出窗口又补不回来。早定色会重复、晚补又来不及——只能推迟结算。

问题？ 推迟之后，为什么还要多一个“已计入”标记？

因为过去的信息会丢：窗口 (c−1,c,c+1)(c-1,c,c+1) 判定过 (r,c)(r,c) 染色，但当时列 cc 还没滑出、不能结算；等列 cc 滑出时，那三列早已不在状态里，无法重新判断。要么当场记下这 3bit，要么把状态撑成 5 列——选前者，mark 位就出现了。

所以状态不用“设计”，用它的唯一职责反推就行：状态 = 为了让下一列能算对、不得不记住的最小信息。下一列要判三连 → 留最近两列的图案；更早窗口的结论会丢 → 留最近两列的标记。12bit 是推导结果，不是要背的清单。

状态转移方程

先把记号固定下来。用 pc∈{0,…,7}p_c \in \{0,\dots,7\} 表示列 cc 的图案，第 rr 位为 11 表示格子 (r,c)(r,c) 画 X；用 mc∈{0,…,7}m_c \in \{0,\dots,7\} 表示列 cc 的"已计入"标记，第 rr 位为 11 表示格子 (r,c)(r,c) 已被判定为红/蓝、但权值还没结算。状态

s=(pA, mA, pB, mB) s = (p_A,\ m_A,\ p_B,\ m_B)

打包了"窗口左列 AA"和"中列 BB"的全部信息，共 1212 bit。

dp[s]dp[s] 的含义是：最近两列恰为状态 ss 时，左侧所有列都已结算完毕的最大分数。它只统计"已落账"的部分，A,BA,B 中被标记的格子权值仍然挂账。

从 ss 再放一列 CC（图案 pCp_C），列 AA 滑出窗口、当场结清，转入新状态 s′=(pB, mB′, pC, mC′)s' = (p_B,\ m_B',\ p_C,\ m_C')，转移方程是

dp′[ s′ ]=max⁡pC∈{0,…,7}{ dp[s]+settle(A) } dp'[\,s'\,] = \max_{p_C \in \{0,\dots,7\}} \Big\{\ dp[s] + \mathrm{settle}(A)\ \Big\}

其中 settle(A)\mathrm{settle}(A) 是列 AA 这一轮结算掉的总权值：列 AA 中凡是位于三连里的格子，红格 +ar,A+a_{r,A}、蓝格 −ar,A-a_{r,A}，并且每个格子只算一次。红/蓝的符号用一个式子统一给出：pA[r]=1p_A[r]=1（X）取 +1+1，pA[r]=0p_A[r]=0（O）取 −1-1，即

sgn(r)=2 pA[r]−1. \mathrm{sgn}(r) = 2\,p_A[r] - 1 .

settle(A)\mathrm{settle}(A) 覆盖三类格子：之前被更早的窗口判定为染色、记在 mAm_A 里的格子；列 AA 自身的纵向三连（pA=0p_A = 0 或 77）；窗口 (A,B,C)(A,B,C) 的横向、两条对角三连命中的 AA 格子。

同一轮里，被窗口三连命中的中列 BB、新列 CC 格子只打标记、不结算：

mB′=mB∪HB,mC′=HC, m_B' = m_B \cup H_B,\qquad m_C' = H_C,

其中 HB,HCH_B, H_C 分别是本轮窗口的横/斜三连命中的 BB、CC 的行集合。

初始状态是"列 0、1 图案任意、无任何标记"：

dp[(p0, 0, p1, 0)]=0,p0,p1∈{0,…,7}. dp\big[(p_0,\ 0,\ p_1,\ 0)\big] = 0,\qquad p_0, p_1 \in \{0,\dots,7\}.

主循环结束后，状态停在最后两列 (n−2,n−1)(n-2, n-1)，它们的账还没结，所以最终答案要在所有状态上再补结一次：

answer=max⁡s{ dp[s]+settle(n−2)+settle(n−1) }, \mathrm{answer} = \max_{s} \Big\{\ dp[s] + \mathrm{settle}(n-2) + \mathrm{settle}(n-1)\ \Big\},

收尾时右侧没有第三列，settle\mathrm{settle} 里只剩"纵向三连 ++ 已有标记"两项。

怎么读这个方程：

  1. max⁡\max 是对新列图案 pCp_C 取的：三列窗口里 A,BA,B 已由状态 ss 唯一确定，pCp_C 是唯一的自由变量，要挑对答案最有利的一种。
  2. 加号左边 dp[s]dp[s] 是过去已固定的分数，右边 settle(A)\mathrm{settle}(A) 是刚滑出窗口的那一列新贡献的分数；列 AA 的权值在此之前从未加过，所以不重不漏。
  3. 方程里只出现最近两列，更早的列既不在状态里、也不在方程里——这就是"三连只跨 3 列"带来的马尔可夫性：列 AA 一旦结清，对未来再无影响。
  4. 标记 mm 是方程能成立的关键：settle(A)\mathrm{settle}(A) 和 mBm_B 的更新必须放在同一次转移里，否则 (A,B,C)(A,B,C) 这条三连下一轮就看不见了，中列 BB 中被它染色的格子会漏账。

DP 转移表格

先看 12bit 状态在代码里的布局（低 6 位是窗口左端“旧列 AA”，高 6 位是“中列 BB”）：

位 0…2 3…5 6…8 9…11
含义 旧列图案 旧列已计入 中列图案 中列已计入

下表把一次转移拆成 5 个逻辑步骤；代码里这 5 步由 gain() 一次完成——第 1 步是开头的落账循环，第 2~5 步是 6 条三连共用的那个循环。用样例 1（n=3n=3，权值全为 1）演示一次完整转移：初始状态是列 0、列 1 全 X 且无标记(dp=0dp=0),枚举新列 j=2 的图案为全 X:

转移步骤 判定的三连 动作 累计 gain
初始状态 旧列 AA=列0: 图案111 已计入000；中列 BB=列1: 图案111 已计入000 dp=0dp=0 0
1. 结算旧列已计入格子 列0 无标记 无 +0
2. 纵向三连 列0 整列 XXX 三格计入并结算 +3，旧列已计入=111
3. 横向三连 三行都是 列0=列1=列2=X 中列、新列打标记 中列已计入=111，新列已计入=111
4. 对角线 ↘ (0,列0)(1,列1)(2,列2) 全 X 打标记 标记已存在，跳过
5. 对角线 ↗ (2,列0)(1,列1)(0,列2) 全 X 打标记 标记已存在，跳过
新状态 旧列 AA=列1(图案111,已计入111)，中列 BB=列2(图案111,已计入111) ndp=0+3=3ndp=0+3=3 3

观察这张表：横向、两条对角线三连都命中了列 1、列 2 的格子，但因为 colored 标记，每个格子只被标记一次；而且列 0 的格子被纵向、横向、两条对角线四个三连同时命中，gain 却只加了 3 而不是 12——这正是"一格只计一次"的体现。

转移完成后，最后两列（列 n−2n-2、n−1n-1）永远不会成为窗口左端，需要单独收尾结算：把已计入的格子权值加上，再补判纵向三连。延续上面的状态（列1、列2 已计入均为 111）：

收尾结算 图案 已计入 结算
列 1（n−2n-2） 111 111 +3
列 2（n−1n-1） 111 111 +3
总计 9

看这张表：列 1、列 2 的格子权值在此刻结算，加上转移阶段结算的列 0 的 3，总分 9，与样例 1 一致。每个格子的权值在整个 DP 中恰好出现一次。

代码

Python 版：

python
#!/usr/bin/env python3
import sys

"""ROJ 20024《棋》的教学版状态压缩 DP。

代码重在描述“3 列滑动窗口 + 染色标记”的思想。
使用字典和四元组保存状态，写法直观，但常数较大，可能无法通过最严数据。
兼容 Python 3.15。
"""


# 三列窗口 A、B、C 中需要检查的 6 条三连。
# 每个格子写成 (行号, 列号)，列号 0/1/2 分别表示 A/B/C。
LINES = (
    ((0, 0), (1, 0), (2, 0)),  # A 列纵向
    ((0, 0), (0, 1), (0, 2)),  # 三条横向
    ((1, 0), (1, 1), (1, 2)),
    ((2, 0), (2, 1), (2, 2)),
    ((0, 0), (1, 1), (2, 2)),  # 对角线 ↘
    ((2, 0), (1, 1), (0, 2)),  # 对角线 ↗
)


def color(pattern: int, row: int) -> int:
    """返回一列第 row 格的棋子：0 表示 O，1 表示 X。"""
    return pattern >> row & 1


def score_sign(pattern: int, row: int) -> int:
    """X 染红贡献为正，O 染蓝贡献为负。"""
    return 1 if color(pattern, row) == 1 else -1


def move(
    col_a: int,
    patterns: tuple[int, int, int],
    mark_a: int,
    mark_b: int,
    weight: list[list[int]],
) -> tuple[int, int, int]:
    """检查窗口 (A, B, C)，结算 A 列，并返回 B、C 的新标记。

    mark 的第 r 位为 1，表示这一格已经确定会染色，但分数还在挂账。
    A 列马上离开窗口，所以本轮结算；B、C 只记录标记，留到以后结算。
    """
    gain = 0
    mark_c = 0

    # A 列中以前已经确定染色的格子，现在统一结算。
    for row in range(3):
        if mark_a >> row & 1:
            gain += weight[row][col_a] * score_sign(patterns[0], row)

    for line in LINES:
        three_colors = [color(patterns[col], row) for row, col in line]
        if not (three_colors[0] == three_colors[1] == three_colors[2]):
            continue

        # 这条线上三个格子都会染色。
        for row, col in line:
            if col == 0:
                # A 列直接计分；用 mark_a 防止一个格子被重复计算。
                if not (mark_a >> row & 1):
                    gain += weight[row][col_a] * score_sign(patterns[0], row)
                    mark_a |= 1 << row
            elif col == 1:
                mark_b |= 1 << row
            else:
                mark_c |= 1 << row

    return gain, mark_b, mark_c


def finish_column(
    col: int, pattern: int, mark: int, weight: list[list[int]]
) -> int:
    """收尾时结算最后两列：已有标记，再补上本列的纵向三连。"""
    if pattern == 0 or pattern == 7:  # OOO 或 XXX
        mark = 7

    gain = 0
    for row in range(3):
        if mark >> row & 1:
            gain += weight[row][col] * score_sign(pattern, row)
    return gain


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    weight = [[next(data) for _ in range(n)] for _ in range(3)]

    # 少于 3 列时只有纵向三连，每列独立选择 XXX 或 OOO。
    if n <= 2:
        answer = 0
        for col in range(n):
            column_sum = sum(weight[row][col] for row in range(3))
            answer += abs(column_sum)
        print(answer)
        return

    # 状态：(A 的图案, A 的标记, B 的图案, B 的标记) -> 最大得分。
    # 一列图案是 0..7：它的 3 个二进制位分别表示三行填 O 还是 X。
    dp: dict[tuple[int, int, int, int], int] = {}
    for pattern_a in range(8):
        for pattern_b in range(8):
            dp[(pattern_a, 0, pattern_b, 0)] = 0

    # 加入新列 C，结算旧列 A，然后窗口由 (A,B) 右移成 (B,C)。
    for col_c in range(2, n):
        col_a = col_c - 2
        next_dp: dict[tuple[int, int, int, int], int] = {}

        for (pattern_a, mark_a, pattern_b, mark_b), old_score in dp.items():
            for pattern_c in range(8):
                patterns = (pattern_a, pattern_b, pattern_c)
                gain, new_mark_b, mark_c = move(
                    col_a, patterns, mark_a, mark_b, weight
                )

                new_state = (pattern_b, new_mark_b, pattern_c, mark_c)
                new_score = old_score + gain
                if new_score > next_dp.get(new_state, -10**100):
                    next_dp[new_state] = new_score

        dp = next_dp

    # 最后两列不会再滑出窗口，需要单独结算。
    answer = -10**100
    for (pattern_a, mark_a, pattern_b, mark_b), old_score in dp.items():
        total = old_score
        total += finish_column(n - 2, pattern_a, mark_a, weight)
        total += finish_column(n - 1, pattern_b, mark_b, weight)
        answer = max(answer, total)

    print(answer)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github:
 * https://github.com/rainboylvx rbook: -> https://rbook.roj.ac.cn
 * https://rbook2.roj.ac.cn rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-26 12:00
 * update_at: 2026-09-26 12:43
 */
// main.cpp：T4 棋(Chess) 正式解
// 12bit 状压 DP：一列 = 图案 pat(3bit) + 已计入标记 mark(3bit)；
// 状态 = 窗口左端"旧列 A" + "中列 B"，共 12bit，枚举新列 C 后结算旧列 A。
// 6 条三连写成常量表 T[6][3]（每个格子是 {行,
// 列偏移}），转移时用一个循环统一判定。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll NEG = -(1LL << 60);
const int MAXN = 1005;
const int SZ = 1 << 12; // 12bit 状态，共 4096 种

// dp[s]：状态 s = (旧列A, 中列B) 时，窗口左端之前的列已全部结算完的最大分数；
//         状态里 mark 标出的格子还只是"挂账"，权值要等它滑出窗口时才加入。
ll dp[SZ];

// ndp[s]：滚动数组的下一层，含义同 dp，用来承接枚举新列 C 之后的转移结果。
ll ndp[SZ];

int n;
ll w[3][MAXN]; // w[行][列]：每个格子的权值

// 得到数字x 的第 k 位是0 还是1
int bit(int x, int k) { return (x >> k) & 1; }

// 列图案 p 第 r 行的染色符号：X(bit=1) 红取 +1，O(bit=0) 蓝取 -1。
int sgn(int p, int r) { return bit(p, r) ? 1 : -1; }

// 三列窗口里的一个格子：行 row(0~2) + 列偏移 col(0=旧列A, 1=中列B, 2=新列C)。
struct offset {
  int row, col;
};

// 6 条三连，每条 3 个格子；只收录"最左格落在 A 列"的直线：
// 1 条 A 列纵向 + 3 条横向 + 2 条对角线。
const offset T[6][3] = {
    {{0, 0}, {1, 0}, {2, 0}}, // 纵向：整列 A
    {{0, 0}, {0, 1}, {0, 2}}, // 横向 行0
    {{1, 0}, {1, 1}, {1, 2}}, // 横向 行1
    {{2, 0}, {2, 1}, {2, 2}}, // 横向 行2
    {{0, 0}, {1, 1}, {2, 2}}, // 对角线 ↘
    {{2, 0}, {1, 1}, {0, 2}}  // 对角线 ↗
};

// 状态编码：s = pA | (mA<<3) | (pB<<6) | (mB<<9)
//  [mB][pB][mA][pA]
inline int encode(int pA, int mA, int pB, int mB) {
  return pA | (mA << 3) | (pB << 6) | (mB << 9);
}

// 解码
inline void decode(int s, int &pA, int &mA, int &pB, int &mB) {
  pA = s & 7;
  mA = (s >> 3) & 7;
  pB = (s >> 6) & 7;
  mB = (s >> 9) & 7;
}

// 结算窗口 (A,B,C) 里的旧列 A：返回本轮 gain，并更新三个"已计入"标记。
// 规则：命中三连的 A 格当场结算（已计入的跳过），B、C 格只打标记。
// colA 列的下标: 第j列, p[3] pA,pB,pC 的状态
// mA mB mC 是否已经计算
ll gain(int colA, int p[3], int &mA, int &mB, int &mC) {
  ll g = 0; // 结果
  // 旧列 A 中"更早窗口已判定染色"的挂账格子，落账
  for (int r = 0; r < 3; r++) {
    if (bit(mA, r)) g += w[r][colA] * sgn(p[0], r);
  }
  // 6 条三连统一判定
  for (int t = 0; t < 6; t++) {
    int v = bit(p[T[t][0].col], T[t][0].row); // 第 t 条三连的第 0 个格子"的颜色
    if (bit(p[T[t][1].col], T[t][1].row) != v) continue;
    if (bit(p[T[t][2].col], T[t][2].row) != v) continue;
    for (int k = 0; k < 3; k++) { // 枚举这一条的三个格子
      int r = T[t][k].row, c = T[t][k].col;
      if (c == 0) { // 旧列 A：计入
        if (!bit(mA, r)) {
          g += w[r][colA] * sgn(p[0], r);
          mA |= 1 << r;
        }
      } else if (c == 1) { // 中列 B：只标记
        mB |= 1 << r;
      } else { // 新列 C：只标记
        mC |= 1 << r;
      }
    }
  }
  return g;
}

// 收尾结算一列：右侧没有第三列，只可能是"已有标记 + 纵向三连"。
ll settle_last(int col, int p, int m) {
  ll g = 0;
  for (int r = 0; r < 3; r++) {
    if (bit(m, r)) g += w[r][col] * sgn(p, r);
  }
  if (p == 0 || p == 7) { // 整列同色 -> 纵向三连
    for (int r = 0; r < 3; r++) {
      if (!bit(m, r)) g += w[r][col] * sgn(p, r);
    }
  }
  return g;
}

// n <= 2：列数不够 3，只有纵向三连，每列独立，直接累加 |列和|。
void solve_small() {
  ll ans = 0;
  for (int c = 0; c < n; c++) {
    ll s = w[0][c] + w[1][c] + w[2][c];
    ans += max(s, -s); // = |s|
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  for (int r = 0; r < 3; r++) {
    for (int c = 0; c < n; c++) {
      cin >> w[r][c];
    }
  }

  if (n <= 2) {
    solve_small();
    return 0;
  }

  for (int s = 0; s < SZ; s++) dp[s] = NEG;
  // 初始：只确定第 0、1 列图案，还没有任何格子计入
  for (int p0 = 0; p0 < 8; p0++) {
    for (int p1 = 0; p1 < 8; p1++) {
      dp[encode(p0, 0, p1, 0)] = 0;
    }
  }

  // ==================== 主循环：一列一列往右推 ====================
  // 进入第 j 轮时，dp 里的状态 s = (旧列 A, 中列 B) 对应 A = j-2、B = j-1，
  // 即"棋盘已确定到第 j-1 列，第 j 列还没放"。
  // 本轮枚举第 j 列的图案 pC，凑出完整三列窗口 (j-2, j-1, j)。
  // 有了这个窗口，列 j-2 的颜色就完全确定了：
  //   - 它作为"右格/中格"的三连（窗口 j-4、j-3）之前已查过，结果记在 mA 里；
  //   - 它作为"左格"的三连（窗口 j-2 本身）以及纵向三连，现在才第一次可见。
  // 所以本轮把列 j-2 的账一次结清，然后窗口整体右移一列。
  for (int j = 2; j < n; j++) {
    int colA = j - 2; // 本轮要结算、并即将滑出窗口左端的列

    // ndp 是下一层 DP，先全部清成不可达
    for (int s = 0; s < SZ; s++) ndp[s] = NEG;

    // 枚举当前层的每一个状态 s = (A 的图案/标记, B 的图案/标记)
    for (int s = 0; s < SZ; s++) {
      if (dp[s] == NEG) continue; // 不可达状态直接跳过

      int pA, mA, pB, mB;
      decode(s, pA, mA, pB, mB); // 拆出 A、B 两列的图案与"已计入"标记

      // 枚举新列 C（第 j 列）的 8 种图案
      for (int pC = 0; pC < 8; pC++) {
        // 用副本承接本轮的新标记（直接改 mA/mB 会污染 dp[s]，因为 s 还要被其它
        // pC 复用）
        int nA = mA, nB = mB, mC = 0;

        // 结算窗口 (A,B,C)：算出列 A 本轮得分 g，并把新标记写回 nA/nB/mC
        int p[3] = {pA, pB, pC};
        ll g = gain(colA, p, nA, nB, mC);

        // 窗口右移一列：新状态是 (B, C)，其中 B 带新标记 nB、C 带新标记 mC
        int ns = encode(pB, nB, pC, mC);

        // 松弛：从状态 s 走一步到 ns，保留更优的分数
        ndp[ns] = max(ndp[ns], dp[s] + g);
      }
    }

    // 本轮所有转移做完，滚动到下一层
    for (int s = 0; s < SZ; s++) dp[s] = ndp[s];
  }

  // 收尾：最后两列永远不会滑到窗口左端，单独结算
  ll ans = NEG;
  for (int s = 0; s < SZ; s++) {
    if (dp[s] == NEG) continue;
    int pA, mA, pB, mB;
    decode(s, pA, mA, pB, mB);
    ll v = dp[s] + settle_last(n - 2, pA, mA) + settle_last(n - 1, pB, mB);
    ans = max(ans, v);
  }
  cout << ans << '\n';
  return 0;
}

复杂度

状态数 212=40962^{12}=4096，每个状态枚举 8 种新列图案，共 n−2n-2 轮主循环，收尾 O(212)O(2^{12})：

  • 时间复杂度：O(n⋅4096⋅8)O(n \cdot 4096 \cdot 8)，n=1000n=1000 时约 3.3×1073.3\times 10^7 次操作；
  • 空间复杂度:O(4096)O(4096),只需滚动两行 DP 数组。

另一种解法：五列窗口（不记账）

主解是“三列窗口 + 染色标记”：只拿到 3 列就急着结算左列，再用标记把更早窗口的信息补回来。这里换一个更直白、但状态更大的思路——攒够信息再结算。

思路

信息覆盖：一条三连最多跨 3 列，所以某一列的格子是否染色，只取决于它左右各 2 列。把这 5 列凑齐，正中间那一列的颜色就完全确定，可以一次性结算。于是不需要任何“已计入”标记。

滑动一下看（中间列逐列被确定）：

窗口 本步新确定 累计已确定 仍待定 状态里留的 4 列
[1][2][3][4][5] [3] ≤\le [3] [4][5] [2][3][4][5]
[2][3][4][5][6] [4] ≤\le [4] [5][6] [3][4][5][6]
[3][4][5][6][7] [5] ≤\le [5] [6][7] [4][5][6][7]
[4][5][6][7][8] [6] ≤\le [6] [7][8] [5][6][7][8]

注意：5 列窗口只确定正中间那一列。[3]、[4] 并不是在窗口 [3…7] 这一步确定的，而是更早的窗口 [1…5]、[2…6] 已经结算过；到 [3…7] 这一步，累计已确定的是 ≤\le [5]，待定的是 [6][7]。

要检查几条三连：结算中间列时，只有"经过中间列"的三连才可能影响它的颜色，其余三连碰不到列 2，判了也白判。3 行 × 5 列里经过列 2 的直线恰好 16 条：横向 9 条（每行 3 条）、纵向 1 条（只有列 2 自己的竖线完整落在窗口内）、右下斜 3 条、右上斜 3 条。代码里用 build_lines() 生成这 16 条，用一张固定的线表代替"对每个格子反推它可能在哪些三连里"的坐标运算。

为什么状态只存 4 列：第 5 列正是“刚要加进来的那一列”。状态里存的是“已经拿到、但还没用于结算”的信息：

text
4 列  →  加新列 = 5 列  →  结算中间列  →  丢掉最旧列  →  又是 4 列

每步恰好丢掉最旧一列，所以状态恒为 4 列，记 f(最近 4 列)f(\text{最近 4 列}) 即可；棋盘外不存在的列用“虚拟列”补齐。

和主解的对比：

何时结算 要不要额外记账 状态
主解（main.cpp） 只有 3 列就结算左列 要（否则更早窗口的信息会丢） 2 列 + 染色标记 = 12bit
本解（main2.cpp） 等到 5 列才结算中列 不要（信息齐了才动手） 4 列图案 = 949^4

一句话：主解是“提前结算 + 记账补信息”，本解是“攒够信息再结算、不记账”。

dp 里到底存了什么

上面说"记 f(最近 4 列)f(\text{最近 4 列})"，落到代码里就是字典 dp：

python
dp: dict[tuple, int]      # 键 = 状态，值 = 分数

key 是状态，回答"未来长什么样"。 元组的每个元素是一列的 3bit 图案（0..7），棋盘外的虚拟列写 None；元组里存的是"以刚读入的那一列结尾的最后若干列"：

python
key = ( ..., p[i-3], p[i-2], p[i-1], p[i] )
处理完 key 的形状 例子
列 0 3 元组 (None, None, 5)
列 1 4 元组 (None, None, 5, 3)
列 2 起 4 元组 (None, 5, 3, 7)

注意 key 永远不是 5 元组——5 列只活在循环体的临时变量 window 里，结算完就把最左一列丢掉：

python
window = state + (pattern,)   # 凑成 5 列，结算中间列
new_state = window[-4:]       # 存回 dp 的仍然只有 4 列

value 是分数，回答"过去赚了多少"。 dp[key] = v 读作：最后这几列的图案是 key 时，更左边那些已经结算完的列的得分总和，最大能到 v。

问题？ key 已经记了状态，为什么还要 value？直接存 key 不行吗？

因为得分是累加的，而 key 只留了最后 4 列，更左边的列已经被丢掉，它们的分数不可能从 key 反推。用样例 2（n=4n=4）跑真实数据，倒数第二轮就出现同一个 key 对应多种历史分数的情况：

text
key = (0, 0, 0, None)
    历史得分 = [83, 84, 85, 87, 88, 95]     ← 6 条不同路径抵达同一状态
    dp 只留   = 95

同一个 key，有的历史只赚 83 分，有的赚 95 分。key 看不出区别，差的那 12 分只能靠 value 记住。

问题？ 那为什么可以只留最大值，把别的都扔掉？

因为转移增量只依赖 key + 新列：

python
window = state + (pattern,)
gain = 0
if len(window) == 5:                                # 凑齐 5 列才轮到中间列结算
    gain = middle_score(window, next_col - 2, weight)
new_score = old_score + gain        # 过去唯一的作用就是这个加法

被丢掉的列再也不可能影响任何未来的 gain。所以到达同一 key 的两条历史面对的"未来"完全一样，未来能加的分也一样 ⇒\Rightarrow 谁的过去分高谁永远赢 ⇒\Rightarrow 低分那条可以安全删除。这就是无后效性，也正是下面这一行的依据：

python
next_dp[new_state] = max(next_dp.get(new_state, NEG), new_score)

如果 dp 只是"状态的集合"，这一行就不存在了——这一行就是 value 这个概念本身。（NEG 只是 max 合并时表示"还没有值"的占位，不会被写进最终结果。）

问题？ 那干脆"直接存每列的状态"、存下整条序列 p0,p1,…,pn−1p_0,p_1,\dots,p_{n-1} 不行吗？

那就是不压缩、不合并，路径数是 8n8^n：n=4n=4 时 4096 条，n=1000n=1000 时约 1090310^{903} 条。DP 的全部价值就是把 8n8^n 条压成不超过 84=40968^4=4096 个 key。压缩必然丢信息：过去各列的图案可以丢（无后效性），但过去赚的分不能丢（它就是答案），于是浓缩成一个标量挂在 key 上。

所以 dp 的本质是一个映射：

dp:状态  ⟶  该状态下能达到的最大累计得分 dp:\quad \text{状态} \;\longrightarrow\; \text{该状态下能达到的最大累计得分}

它对应的"状态集"不是预先枚举好的，而是被 max 合并动态长出来的：多条路径撞上同一个 key 才产生一个状态，而"状态存在"这件事，就是它的 value 不是 NEG。main2.cpp 用 C++ 重写时，把这层意思换成了定长数组 dp[9^4]：

cpp
for (int s = 0; s < SZ; s++) dp[s] = NEG;
if (dp[s] == NEG) continue;      // 等价于"这个 key 不在字典里"

数组是稠密预分配的，字典是稀疏懒生长的，两者概念完全一样：key 管未来，value 管过去，缺一不可。

代码

main2.py 是 Python 教学原型，用字典存状态，慢但一眼能看懂。它把"窗口里哪些格子被染色"这件重复劳动也做成了预处理：先用 build_lines() 按四个方向族生成"经过中间列"的三连常量表 LINES（横向 9 + 纵向 1 + 两个斜向各 3，共 16 条），再把 959^5 种窗口的"中间列染色掩码"整表算进 COLORED，主循环里只剩一次查表：

python
#!/usr/bin/env python3
"""ROJ 20024《棋》：优先讲清思想的五列窗口 DP。

写法兼容 Python 3.15。它省去了染色标记，容易理解，但运行速度较慢。
"""

NONE = 8          # 棋盘外的虚拟列；状态里写成 None，编成整数时才变成 8
NEG = -10**100


def get_color(pattern: int, row: int) -> int:
    """一列用 3 bit 表示；第 row 位是 0 表示 O，是 1 表示 X。"""
    return pattern >> row & 1


# 窗口是 3 行 x 5 列。长度为 3 的直线有很多条，但本轮只结算中间列（列 2），
# 所以只保留"经过列 2"的线。每条线写成 3 个 (行, 列) 格子，行取 0..2，列取 0..4：
#
#        列 0   列 1   列 2   列 3   列 4
#   行 0   .      .      .      .      .
#   行 1   .      .      .      .      .
#   行 2   .      .      .      .      .
#                 ↑ 中间列，本轮的结算对象
def build_lines():
    """生成 3 行 x 5 列窗口里所有经过中间列的三连，共 16 条。"""
    lines = []

    # 横向 9 条：每行都有 3 条（起点列 0 / 1 / 2），条条都经过列 2，生成：
    #   ((0,0),(0,1),(0,2))  ((0,1),(0,2),(0,3))  ((0,2),(0,3),(0,4))
    #   ((1,0),(1,1),(1,2))  ((1,1),(1,2),(1,3))  ((1,2),(1,3),(1,4))
    #   ((2,0),(2,1),(2,2))  ((2,1),(2,2),(2,3))  ((2,2),(2,3),(2,4))
    for r in range(3):
        for c in range(3):
            lines.append(((r, c), (r, c + 1), (r, c + 2)))

    # 纵向 1 条：只有列 2 自己的竖线完整落在窗口里，生成：
    #   ((0,2),(1,2),(2,2))
    lines.append(((0, 2), (1, 2), (2, 2)))

    # 右下斜 3 条：从第 0 行走到第 2 行，行 +1、列 +1，生成：
    #   ((0,0),(1,1),(2,2))  ((0,1),(1,2),(2,3))  ((0,2),(1,3),(2,4))
    for c in range(3):
        lines.append(((0, c), (1, c + 1), (2, c + 2)))

    # 右上斜 3 条：从第 0 行走到第 2 行，行 +1、列 -1，生成：
    #   ((0,2),(1,1),(2,0))  ((0,3),(1,2),(2,1))  ((0,4),(1,3),(2,2))
    for c in range(3):
        lines.append(((0, c + 2), (1, c + 1), (2, c)))

    return tuple(lines)


LINES = build_lines()


def colored_mask(window) -> int:
    """窗口中间列哪几行位于某个三连中：第 row 位为 1 表示 (row, 2) 被染色。"""
    mask = 0

    for cells in LINES:
        # 三连里只要有一格是虚拟列（棋盘外），这条线就不成立
        if any(window[c] is None for _, c in cells):
            continue

        # 三个格子同色，才构成一条三连
        r0, c0 = cells[0]
        color = get_color(window[c0], r0)
        if not all(get_color(window[c], r) == color for r, c in cells):
            continue

        # 只登记中间列的行
        for r, c in cells:
            if c == 2:
                mask |= 1 << r

    return mask


def window_code(window) -> int:
    """5 列窗口 -> 9 进制整数（window[0] 是最高位，window[4] 是最低位）。"""
    code = 0
    for pattern in window:
        code = code * 9 + (NONE if pattern is None else pattern)
    return code


def decode_window(code):
    """9 进制整数 -> 5 列窗口，是 window_code 的逆运算。"""
    window = [None] * 5
    for i in range(4, -1, -1):      # window[4] 是最低位
        p = code % 9
        window[i] = None if p == NONE else p
        code //= 9
    return window


# 预处理：窗口一共 9^5 种，每种窗口"中间列哪几行被染色"先整表算好。
# 主循环里同一个窗口会反复出现，查表比每次重判 16 条三连省事得多。
COLORED = bytearray(9 ** 5)
for _code in range(9 ** 5):
    COLORED[_code] = colored_mask(decode_window(_code))


def middle_score(window, col: int, weight: list[list[int]]) -> int:
    """五列都已知时，计算正中间这一列的完整得分。"""
    mask = COLORED[window_code(window)]
    pattern = window[2]
    score = 0

    for row in range(3):
        if mask >> row & 1:
            sign = 1 if get_color(pattern, row) == 1 else -1
            score += sign * weight[row][col]

    return score


def solve() -> None:
    n = int(input())
    weight = [list(map(int, input().split())) for _ in range(3)]

    # 状态是最近至多四列的图案，值是已经结算的最大得分。
    # 开头先放两个 None，表示棋盘左边的两列不存在。
    dp = {(None, None): 0}

    # 枚举 n 列真实棋盘，再补两个 None，让最后两列也能成为窗口中心。
    for next_col in range(n + 2):
        choices = range(8) if next_col < n else (None,)
        next_dp = {}

        for state, old_score in dp.items():
            for pattern in choices:
                window = state + (pattern,)
                gain = 0

                # 凑齐五列后，中间列左右各有两列，它的颜色已经完全确定。
                if len(window) == 5:
                    middle_col = next_col - 2
                    gain = middle_score(window, middle_col, weight)

                new_state = window[-4:]
                new_score = old_score + gain
                next_dp[new_state] = max(next_dp.get(new_state, NEG), new_score)

        dp = next_dp

    print(max(dp.values()))


if __name__ == "__main__":
    solve()

main3.py 是同一算法的 Pythonic 短写法，和 main2.py 一一对应：四个列表推导直接写出那张 16 条的线表，再用 functools.cache 把"窗口 → 中间列染色掩码"按需缓存——相当于把 COLORED 那张表改成懒加载，于是 window_code() / decode_window() 和建表循环全部消失，代码从 151 行降到不到 90 行。代价是启动时不再预热，运行时要多一次缓存查找：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-28 12:53
# update_at: 2026-09-28 16:58

import sys
from collections.abc import Iterable
from functools import cache

NEG = -10**100


def get_color(pattern: int, row: int) -> int:
    """取一列第 row 位的颜色：0 表示 O，1 表示 X。"""
    return pattern >> row & 1


# 窗口里所有"经过中间列（列 2）"的三连，共 16 条；每条写成 3 个 (行, 列) 格子。
# 本轮只结算中间列，所以别的线一概不要。
LINES = (
    [((r, c), (r, c + 1), (r, c + 2)) for r in range(3) for c in range(3)]  # 横向 9 条
    + [((0, 2), (1, 2), (2, 2))]                                           # 纵向 1 条
    + [((0, c), (1, c + 1), (2, c + 2)) for c in range(3)]                  # 右下斜 3 条
    + [((0, c + 2), (1, c + 1), (2, c)) for c in range(3)]                  # 右上斜 3 条
)


@cache
def colored_mask(window: tuple[int | None, ...]) -> int:
    """窗口中间列哪几行位于某个三连中：第 row 位为 1 表示 (row, 2) 被染色。

    窗口是元组（元素为 0..7 或 None），天然可哈希，所以能直接当缓存键：
    同一个窗口只算一次，效果和 main2.py 里那张 COLORED 表一样，但按需生成。
    """
    mask = 0
    for cells in LINES:
        if any(window[c] is None for _, c in cells):
            continue                                    # 有格子落在棋盘外
        if len({get_color(window[c], r) for r, c in cells}) == 1:  # 三格同色
            mask |= sum(1 << r for r, c in cells if c == 2)        # 只登记中间列
    return mask


def middle_score(window: tuple[int | None, ...], col: int, weight: list[list[int]]) -> int:
    """五列都已知时，计算正中间那一列（棋盘第 col 列）的完整得分。"""
    mask = colored_mask(window)
    middle = window[2]                                       # 窗口五列里结算的就是第 2 列
    return sum(
        (1 if get_color(middle, r) else -1) * weight[r][col]  # X 红 +，O 蓝 -
        for r in range(3)
        if mask >> r & 1
    )


def advance(dp: dict[tuple[int | None, ...], int], choices: Iterable[int | None],
            col: int, weight: list[list[int]]) -> dict[tuple[int | None, ...], int]:
    """滑动一列：每个旧状态接上新列的图案，凑满五列时就结算窗口中心那一列。"""
    nxt: dict[tuple[int | None, ...], int] = {}
    for state, score in dp.items():
        for pattern in choices:
            window = state + (pattern,)
            gain = middle_score(window, col, weight) if len(window) == 5 else 0
            new_state = window[-4:]                          # 只留最近 4 列当下一轮的状态
            nxt[new_state] = max(nxt.get(new_state, NEG), score + gain)
    return nxt


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    weight = [[next(data) for _ in range(n)] for _ in range(3)]

    # 状态是最近至多 4 列的图案。左侧两列在棋盘外，先垫两个 None 当窗口左边界，
    # 这样第 0 列会在 next_col = 2 时正好落到窗口中心被结算。
    dp: dict[tuple[int | None, ...], int] = {(None, None): 0}

    for next_col in range(n + 2):
        # 棋盘内的列有 8 种图案；末尾追加两个 None，把最后两列也顶到窗口中心。
        choices = range(8) if next_col < n else (None,)
        dp = advance(dp, choices, next_col - 2, weight)

    # 补的 None 已经把每一列都结算过，剩下的状态只比总分。
    print(max(dp.values()))


if __name__ == "__main__":
    solve()

main2.cpp 是同一思路的 C++ 实现，用同一张 LINES 表（build_lines() 生成）判断三连，同样把 959^5 种窗口的"中间列染色情况"预处理进 colored_mask[]，主循环里 O(1)O(1) 查表，n=1000n=1000 也能跑进时限：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-27 09:05
 * update_at: 2026-09-27 22:56
 */
// main2.cpp：T4 棋(Chess) 教学版——"五列窗口"DP（对应 main2.py）。
//
// 和 main.cpp 的"三列窗口 + 染色标记"不同，这里换个更好懂的切入角度：
//   一条三连最多跨 3 列，所以某一列的格子"是否染色"只取决于它左右各 2 列。
//   等一列左右各 2 列都确定了（凑齐 5 列窗口），就能一次性算出这一整列的得分。
// 好处：状态里不用再存"这一格是否已计入"的标记，思想更直白。
// 代价：状态要记最近 4 列；棋盘左边/右边不存在的列用"虚拟列"补上。
//
// 为了让 n = 1000 也能跑进 1s，这里多做一步预处理：
//   染色判断只跟"5 列窗口"有关，跟具体列号/权值无关；
//   而同一个窗口会被大量 (状态, 新列图案) 组合反复查询。
//   所以先把所有窗口的"中间列染色情况"算好，主循环里 O(1) 查表。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll NEG = -(1LL << 60);
const int MAXN = 1005;
const int ROWS = 3;      // 棋盘固定 3 行

const int PAT_CNT = 8;   // 一列的图案：3bit，0..7（bit r = 1 表示第 r 行是 X）
const int NONE = 8;      // 虚拟列（棋盘外），用一个额外取值 8 表示
const int BASE = 9;      // 状态按 9 进制存，每一位 0..8

const int SZ = BASE * BASE * BASE * BASE; // 状态：最近 4 列，9^4 = 6561
const int WIN_SZ = SZ * BASE;             // 窗口：最近 5 列，9^5 = 59049

int n;
ll w[ROWS][MAXN];        // w[行][列]：每个格子的权值

// 取一列图案 pattern 的第 row 位：1 表示 X，0 表示 O。
inline int color(int pattern, int row) {
    return (pattern >> row) & 1;
}

/* ---------------- 窗口里"经过中间列"的三连 ----------------
 * 窗口是 3 行 x 5 列。长度为 3 的直线有很多条，但本轮只结算中间列（列 2），
 * 所以只保留"经过列 2"的线。每条线写成 3 个格子。
 *
 *        列 0   列 1   列 2   列 3   列 4
 *   行 0   .      .      .      .      .
 *   行 1   .      .      .      .      .
 *   行 2   .      .      .      .      .
 *                 ↑ 中间列，本轮的结算对象
 */
const int LINE_CNT = 16;      // 横向 9 + 纵向 1 + 右下斜 3 + 右上斜 3
int line_r[LINE_CNT][3];      // 每条线 3 个格子的行
int line_c[LINE_CNT][3];      // 每条线 3 个格子的列

void build_lines() {
    int cnt = 0;

    // 横向 9 条：每行都有 3 条（起点列 0 / 1 / 2），条条都经过列 2，生成：
    //   ((0,0),(0,1),(0,2))  ((0,1),(0,2),(0,3))  ((0,2),(0,3),(0,4))
    //   ((1,0),(1,1),(1,2))  ((1,1),(1,2),(1,3))  ((1,2),(1,3),(1,4))
    //   ((2,0),(2,1),(2,2))  ((2,1),(2,2),(2,3))  ((2,2),(2,3),(2,4))
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < 3; c++) {
            for (int k = 0; k < 3; k++) {
                line_r[cnt][k] = r;
                line_c[cnt][k] = c + k;
            }
            cnt++;
        }
    }

    // 纵向 1 条：只有列 2 自己的竖线完整落在窗口里，生成：
    //   ((0,2),(1,2),(2,2))
    for (int k = 0; k < 3; k++) {
        line_r[cnt][k] = k;
        line_c[cnt][k] = 2;
    }
    cnt++;

    // 右下斜 3 条：从第 0 行走到第 2 行，行 +1、列 +1，生成：
    //   ((0,0),(1,1),(2,2))  ((0,1),(1,2),(2,3))  ((0,2),(1,3),(2,4))
    for (int c = 0; c < 3; c++) {
        for (int k = 0; k < 3; k++) {
            line_r[cnt][k] = k;
            line_c[cnt][k] = c + k;
        }
        cnt++;
    }

    // 右上斜 3 条：从第 0 行走到第 2 行，行 +1、列 -1，生成：
    //   ((0,2),(1,1),(2,0))  ((0,3),(1,2),(2,1))  ((0,4),(1,3),(2,2))
    for (int c = 0; c < 3; c++) {
        for (int k = 0; k < 3; k++) {
            line_r[cnt][k] = k;
            line_c[cnt][k] = c + 2 - k;
        }
        cnt++;
    }
}

// 窗口中间列哪几行位于某个三连中：第 row 位 = 1 表示 (row, 2) 被染色。
// window[c] 取值 0..7 是真实列，8(NONE) 表示棋盘外的虚拟列。
int colored_mask_of(const int window[5]) {
    int mask = 0;

    for (int i = 0; i < LINE_CNT; i++) {
        // 三连里只要有一格是虚拟列（棋盘外），这条线就不成立
        int r0 = line_r[i][0], c0 = line_c[i][0];
        if (window[c0] == NONE) continue;

        // 三个格子同色，才构成一条三连
        int target = color(window[c0], r0);
        bool same = true;
        for (int k = 1; k < 3; k++) {
            int r = line_r[i][k], c = line_c[i][k];
            if (window[c] == NONE || color(window[c], r) != target) { same = false; break; }
        }
        if (!same) continue;

        // 只登记中间列的行
        for (int k = 0; k < 3; k++) {
            if (line_c[i][k] == 2) mask |= 1 << line_r[i][k];
        }
    }

    return mask;
}

/* ---------------- 状态 / 窗口的编码 ----------------
 * 把若干列图案按 9 进制拼成一个整数（低位是最旧的一列）。
 * 4 位 -> 状态，5 位 -> 窗口。
 */
inline int encode4(int d0, int d1, int d2, int d3) {
    return d0 + d1 * BASE + d2 * BASE * BASE + d3 * BASE * BASE * BASE;
}
inline void decode4(int s, int d[4]) {
    for (int i = 0; i < 4; i++) {
        d[i] = s % BASE;
        s /= BASE;
    }
}

/* ---------------- 预处理：窗口 -> 中间列的染色情况 ----------------
 * colored_mask[code] 的第 r 位 = 1，表示该窗口中间列第 r 行会被染色。
 * 同一个窗口在 DP 中会被查很多次，预处理后每次只需一次数组访问。
 */
static unsigned char colored_mask[WIN_SZ];

void precompute_colored() {
    for (int code = 0; code < WIN_SZ; code++) {
        int window[5];
        int t = code;
        for (int i = 0; i < 5; i++) { // 拆出 5 个 9 进制位
            window[i] = t % BASE;
            t /= BASE;
        }
        colored_mask[code] = (unsigned char)colored_mask_of(window);
    }
}

// 5 列都确定时，算出正中间列（对应棋盘第 col 列）的完整得分。
// middle_pattern 就是中间列的图案，用来定符号（X 红 +，O 蓝 -）。
ll middle_score(int code, int middle_pattern, int col) {
    int mask = colored_mask[code];
    ll score = 0;
    for (int row = 0; row < ROWS; row++) {
        if (!((mask >> row) & 1)) continue; // 没染色就不计分
        int sign = (color(middle_pattern, row) == 1) ? 1 : -1;
        score += sign * w[row][col];
    }
    return score;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < n; c++) {
            cin >> w[r][c];
        }
    }

    build_lines();
    precompute_colored();

    static ll dp[SZ], ndp[SZ]; // dp[状态] = 已经结算完的最大得分
    for (int s = 0; s < SZ; s++) dp[s] = NEG;

    // 初始：最近 4 列都是"虚拟列"（棋盘左边不存在）
    dp[encode4(NONE, NONE, NONE, NONE)] = 0;

    // 枚举 n 列真实棋盘，再补 2 列虚拟列，
    // 让最后两列也能各自成为一次"窗口正中间"被结算。
    for (int next_col = 0; next_col < n + 2; next_col++) {
        for (int s = 0; s < SZ; s++) ndp[s] = NEG;

        // 真实列可选图案 0..7；补出来的虚拟列只能是 NONE
        int lo = 0, hi = PAT_CNT;
        if (next_col >= n) { lo = NONE; hi = NONE + 1; }

        for (int s = 0; s < SZ; s++) {
            if (dp[s] == NEG) continue; // 不可达状态
            int d[4];
            decode4(s, d);

            for (int pattern = lo; pattern < hi; pattern++) {
                // 旧 4 列 + 新列 = 5 列窗口；顺手算出它的 9 进制编码
                int code = encode4(d[0], d[1], d[2], d[3]) + pattern * SZ;

                ll gain = 0;
                int middle_col = next_col - 2; // 窗口正中对应的棋盘列
                if (0 <= middle_col && middle_col < n) {
                    // 中间列左右各 2 列都齐了，可以结算它的整列得分
                    gain = middle_score(code, d[2], middle_col);
                }

                // 窗口右移一列：丢掉最旧的 d0，新状态是 (d1, d2, d3, pattern)
                int ns = encode4(d[1], d[2], d[3], pattern);
                ndp[ns] = max(ndp[ns], dp[s] + gain);
            }
        }

        for (int s = 0; s < SZ; s++) dp[s] = ndp[s];
    }

    // 全部列都已结算，取最大得分
    ll ans = NEG;
    for (int s = 0; s < SZ; s++) ans = max(ans, dp[s]);
    cout << ans << '\n';
    return 0;
}

复杂度

  • 状态数 94=65619^4=6561，每个状态枚举 8 种新列图案，共 n+2n+2 轮：O(n⋅94⋅8)O(n \cdot 9^4 \cdot 8)；
  • 窗口/掩码的预处理 95=590499^5=59049 种窗口（main3.py 用 functools.cache 按需缓存，只算实际遇到的那部分）；
  • 空间 O(94+95)O(9^4 + 9^5)。

总结

这道题的关键是把"格子颜色"的判定从局部视角换成窗口视角:横向/斜向三连跨相邻 3 列,所以当一列滑出 3 列窗口时,它的颜色已经确定。窄带状压 DP 的通用套路就是–先找"未来只依赖过去哪段紧凑信息"(这里是相邻 2 列),再用 colored 标记解决"一个对象被多个结构重复命中"的计权问题。这种“标记去重”的思想在网格类 DP 里很常用。

本题还演示了两种“有限记忆”策略：主解提前结算 + 用标记补回已经丢失的信息（状态更小），另一解攒够 5 列信息再结算、完全不用标记（状态更大但更直白）——它们都是“只保留够用的过去”这一思想的变体。