题解：P12613 [CCC 2025 Junior] Connecting Territories

· · 题解

题目大意

给定一个 r\times c 的网格。分别从左往右从上往下填上 1 至 m 的循环数列，问从第一行开始每次可以走左下，正下，右下，走到最后一行的最小值。

解题思路

考虑DP。

定义状态

用 f(i,j) 表示从第一行走到第 i 行第 j 列经过路径的最小值。

分解子问题

f(i,j)= \min(f(i-1,j-1),f(i-1,j),f(i-1,j+1))+a_{ij}

其中 a_{ij}=((i-1)\times c+j)\bmod m+1 但是本题不建议用取模运算，会TLE，令一个变量 a 不断自增，若超过 m 就初始化为 1。

边界状态

f(0,j) = 0

问题答案

ans=\min\limits_{j=1}^n f(n,j)

效率分析

时间复杂度和空间复杂度都为 O(r\times c)。

分析完发现 r,c\le 2\times 10^4 肯定炸空间了，观察转移方程当前行状态只会从上一行转移，并且答案只需要从最后一行的状态获取。考虑奇偶滚动数组优化。

代码实现

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll r, c, m, dp[2][20005], ans = 1e18, a;
int main() {
    cin >> r >> c >> m;
    memset(dp, 0x3f, sizeof dp);
    for (int j = 1; j <= c; j++)
        dp[0][j] = 0;
    for (int i = 1; i <= r; ++i) {
        int now = i & 1, bef = (i - 1) & 1; //当前行和上一行的奇偶
        for (int j = 1; j <= c; ++j) {
            a++;
            if (a > m) a = 1;
            dp[now][j] = min(dp[bef][j], min(dp[bef][j - 1], dp[bef][j + 1])) + a;
            if (i == r) ans = min(ans, dp[now][j]);
        }
    }
    cout << ans;
    return 0;
}