D. Shift + Esc 题解

题目大意

给定 $n$ 行 $m$ 列的非负整数网格，你从 $(1,1)$ 出发，只能向下/向右移动到 $(n,m)$。 在移动前，你可以对任意行执行任意次循环左移1位操作：

• 对第 $i$ 行左移 $shift$ 次，代价为 $k \times shift$；
• 移动后路径经过的单元格数值和为 $y$；
• 总代价 = 操作总代价 + 路径和。

求最小总代价。

约束：$1 \le n,m \le 200$，所有测试用例 $n \cdot m \le 5 \times 10^4$，数值范围可达 $10^9$。

核心思路

关键观察

1. 移动特性：从起点到终点，每行只会停留一个最终列位置（从上行下移到当前行后，只能向右走，最终停在某一列，再下移到下一行）。
2. 循环移位：一行左移 $m$ 次等价于不移位，因此每行只需枚举 $0 \sim m-1$ 次移位即可。
3. 动态规划：用DP记录「处理完前 $i$ 行，停在第 $i$ 行第 $j$ 列」的最小代价，完美适配问题的无后效性。

状态定义

$dp[i][j]$：处理完前 $i$ 行，最终停在第 $i$ 行第 $j$ 列的最小总代价。

状态转移

1. 枚举第 $i$ 行的移位次数 $shift$（$0 \le shift < m$）；
2. 从第 $i-1$ 行的任意列转移而来，加上当前行移位代价 + 路径数值和；
3. 利用行内只能向右移动的特性，用两次环形遍历优化区间最小值转移。

完整AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// 数组开至511，满足n,m<=200的约束
ll dp[511][511], a[511][511];

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    // 输入网格，下标从1开始（行）、0开始（列）方便取模运算
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    // 初始化DP数组为无穷大（1e18 避免long long溢出）
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < m; ++j) {
            dp[i][j] = 1e18;
        }
    }
    dp[0][0] = 0; // 初始状态：第0行第0列，代价为0

    // 逐行处理
    for (int i = 1; i <= n; ++i) {
        // 枚举当前行的循环左移次数 shift (0~m-1)
        for (int shift = 0; shift < m; ++shift) {
            vector<ll> tmp(m, 1e18);
            // 第一步：从i-1行转移，加上当前列的值 + 移位代价
            for (int j = 0; j < m; ++j) {
                tmp[j] = dp[i-1][j] + a[i][(j + shift) % m] + 1LL * k * shift;
            }

            // 两次环形遍历更新最小值：行内只能向右走，递推最小代价
            for (int j = 0; j < m; ++j) {
                tmp[j] = min(tmp[j], tmp[(j + m - 1) % m] + a[i][(j + shift) % m]);
            }
            for (int j = 0; j < m; ++j) {
                tmp[j] = min(tmp[j], tmp[(j + m - 1) % m] + a[i][(j + shift) % m]);
            }

            // 更新当前行的DP值
            for (int j = 0; j < m; ++j) {
                dp[i][j] = min(dp[i][j], tmp[j]);
            }
        }
    }

    // 答案：第n行最后一列的最小代价
    cout << dp[n][m-1] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

代码详解

1. 初始化

• dp 数组初始化为 $10^{18}$（无穷大），代表初始状态不可达；
• dp[0][0] = 0：虚拟的第0行第0列，作为起点。

2. 逐行枚举移位

对每一行 $i$，枚举所有可能的移位次数 $shift$：

• 计算基础代价：上一行的代价 + 当前单元格数值 + 移位代价；
• 两次环形遍历：利用只能向右移动的规则，递推求出当前行所有列的最小代价（等价于区间最小值优化）。

3. 答案输出

终点是第 $n$ 行最后一列，对应下标 dp[n][m-1]。

复杂度分析

• 时间复杂度：$\mathcal{O}(t \cdot n \cdot m^2)$
  • $n,m \le 200$，单组用例 $200 \times 200^2 = 8 \times 10^6$；
  • 总数据量 $5 \times 10^4$，完全满足时间限制。
• 空间复杂度：$\mathcal{O}(n \cdot m)$，数组大小完全适配题目约束。

优化说明

1. 数据类型：全程使用 long long，避免 $10^9$ 数值相加溢出；
2. 输入优化：加 ios::sync_with_stdio(false);cin.tie(nullptr); 加速大数据输入；
3. 移位枚举：仅枚举 $0 \sim m-1$ 次，避免无效计算。