2021第十二届蓝桥杯省赛C++A组：路径（动态规划）

题目描述

 解题思路

对于该题，两节点之差绝对值大于21则不连通，故转移时只需考虑与该节点之差绝对值小于21的节点。

考虑动态规划解法，dp[i]表示为节点1到节点i的最短距离，初始状态dp[1]=0，动态转移方程为dp[j] = min(dp[i] + get_length(i, j), dp[j])，即结点j是否被选入路径中由dp[i]+结点i和j之间的距离决定，最终输出dp[2021]即为正确结果

答案：10266837

附代码

#include<bits/stdc++.h>
using namespace std;
int get_length(int a, int b) {
	for (int i = max(a, b); i <= a * b; i++) {
		if (i % a == 0 && i % b == 0)
			return i;
	}
	return 0;
}
int main() {
	int dp[2022];
	for (int i = 0; i < 2022; i++) {
		dp[i] = INT_MAX;
	}
	dp[1] = 0;
	for (int i = 1; i < 2022; i++) {
		for (int j = i + 1; j <= i + 21&&j<2022; j++) {
			dp[j] = min(dp[i] + get_length(i, j), dp[j]);
		}
	}
	cout << dp[2021];
	return 0;
}