一、题意正式重述

给定一个 $n\times m$ 的矩阵 $A$，元素取值范围为 $[1,k]$。 矩阵中部分格子已填充，未填充的格子用 $-1$ 表示。

你需要将所有 $-1$ 填充为 $[1,k]$ 中的任意数字，最大化矩阵的美观度：

定义：

• $c_{u,i}$：第 $i$ 行中数字 $u$ 出现的次数。

美观度公式：

$$\boldsymbol{ans} = \sum_{u=1}^{k} \sum_{i=1}^{n-1} c_{u,i} \cdot c_{u,i+1} $$

输出最大美观度。

数据范围

• $2\le n,m\le 2\times 10^5$
• $n\cdot m \le 6\times 10^5$
• $\sum n\cdot m \le 6\times 10^5$
• $1\le k \le n\cdot m$

---

二、核心数学转化（最关键一步）

我们可以对美观度公式进行代数变形，这是整道题的突破口：

原始式子

$$\sum_{u=1}^k \sum_{i=1}^{n-1} c_{u,i}\,c_{u,i+1}$$

变形后（等价）

令：

• $x_{u,i}$：第 $i$ 行中数字 $u$ 的最终个数
• $f_{u,i}$：第 $i$ 行中已经固定的 $u$ 的个数
• $r_i$：第 $i$ 行中**空格（$-1$）**的数量

则对于每一行 $i$，有约束：

$$\sum_{u=1}^k x_{u,i} = m,\quad x_{u,i} \ge f_{u,i} $$

最终目标

最大化：

$$\sum_{i=1}^{n-1}\left( \sum_{u=1}^k x_{u,i}\,x_{u,i+1} \right) $$

---

三、贪心结论

要最大化相邻行相同数字计数乘积之和，最优策略是：

最优策略

让相邻两行的空格尽可能填充相同的数字，使每一对 $x_{u,i}\cdot x_{u,i+1}$ 之和最大。

这是一个相邻行配对最大化问题，可以用动态规划 + 状态压缩在线性时间内解决。

---

四、标程核心设计思想

1. 状态定义

标程使用滚动 DP 处理相邻两行：

• $dp[u]$：表示以数字 $u$ 作为当前行重点匹配对象时的最大贡献
• $a, b$：维护全局最优值与累计空白贡献
• $cntp[u], cntq[u]$：上一行 / 当前行数字 $u$ 的固定数量
• $cntP, cntQ$：上一行 / 当前行空格数量

2. 转移方式

每次读入新的一行，执行：

1. 计算固定数字能产生的最大贡献
2. 计算空白填充能产生的最大贡献
3. 用 $\max$ 更新 DP 状态
4. 滚动数组，丢弃无用历史状态

3. 时间复杂度

$O(\sum n\cdot m)$，完全符合 $6\times 10^5$ 限制。

---

五、标程逐行详细解析

1. 快速 IO 模块

namespace FastIO { ... }; using namespace FastIO;

作用：加速大量数据的读写，保证 $5$ 秒时限内通过。

---

2. 变量定义

int n, m, k;
ll cntP, cntQ;        // 上一行、当前行空格数
vector<int> vep, veq; // 上一行、当前行元素
vector<int> cntp, cntq;// 上一行、当前行各数字计数
vector<int> vis;      // 防重复处理标记
vector<ll> dp;        // 核心 DP 数组
ll a, b, v, ext;      // 全局最优状态

---

3. 工具函数

auto get = [&](int x) -> int { return (~x) ? x : 0; };

将 $-1$ 转为 $0$ 方便统计。

auto read_q = [&]() -> void;

读取一行，并更新数字计数与空格数。

auto roll = [&]() -> void;

滚动数组：当前行变上一行，准备读下一行。

---

4. DP 主循环

for (int i = 2; i <= n; ++i) {
    read_q();           // 读入当前行
    ll max_dp = ...;    // 全局最大值
    
    // 用固定数字更新最大值
    for (int k : vep) if (~k) ...
    for (int k : veq) if (~k) ...
    
    // 更新 DP 状态
    for (int k : vep) if ((~k) && vis[k] != i) ...
    for (int k : veq) if ((~k) && vis[k] != i) ...
    
    // 更新全局最优
    a = max(...), b += ...;
    roll();
}

---

5. 最终答案

print<ll>(max(a, v + b) + ext, '\n');

$$\boldsymbol{ans} = \max(a,\ v+b) + ext$$

• $\max(a, v+b)$：空白填充的最大贡献
• $ext$：固定数字产生的贡献

---

六、标程为什么能得到正确答案？

1. 数学转化正确 美观度等价于相邻行数字计数乘积和，最大化该和等价于尽可能让相邻行数字分布一致。

2. DP 状态设计正确 $dp[u]$ 记录以数字 $u$ 为核心的最优解，覆盖所有可能最优情况。

3. 转移正确 每次转移同时考虑：

   • 固定数字的贡献
   • 空白填充的最优选择
   • 全局最优解

4. 复杂度正确 每行仅遍历 $O(m)$ 个数字，总复杂度 $O(\sum nm)$。

---

七、样例验证（样例 1）

输入：

3 3 3
1 2 2
3 1 3
3 2 1

各行计数：

• 行 $1$：$c_1=1,\ c_2=2,\ c_3=0$
• 行 $2$：$c_1=1,\ c_2=0,\ c_3=2$
• 行 $3$：$c_1=1,\ c_2=1,\ c_3=1$

计算美观度：

$$\begin{align*} &1\cdot 1 + 1\cdot 1 \\ +\ &2\cdot 0 + 0\cdot 1 \\ +\ &0\cdot 2 + 2\cdot 1 \\ =\ &4 \end{align*} $$

标程输出：$4$，与样例一致。

---

八、总结（最简版）

这道题表面是矩阵填充，本质是：

核心问题

给定相邻行约束，求

$$\max \sum_{i=1}^{n-1}\sum_{u=1}^k x_{u,i}x_{u,i+1} $$

解法

滚动 DP + 贪心填充空白

标程复杂度

$$O(\sum n\cdot m)$$

最终答案公式

$$\boxed{ans = \max(a,\ v+b) + ext}$$