专栏文章

题解：P12613 [CCC 2025 Junior] Connecting Territories

kkuaiCreator
P12613题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip3mg8r
此快照首次捕获于
2025/12/03 05:37
3 个月前
此快照最后确认于
2025/12/03 05:37
3 个月前
查看原文

题目大意

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

解题思路

考虑DP。

定义状态

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

分解子问题

f(i,j)=min⁡(f(i−1,j−1),f(i−1,j),f(i−1,j+1))+aijf(i,j)= \min(f(i-1,j-1),f(i-1,j),f(i-1,j+1))+a_{ij}
其中 aij=((i−1)×c+j) mod m+1a_{ij}=((i-1)\times c+j)\bmod m+1 但是本题不建议用取模运算，会TLE，令一个变量 aa 不断自增，若超过 mm 就初始化为 11。

边界状态

f(0,j)=0f(0,j) = 0

问题答案

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

效率分析

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

代码实现

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...