P12381 [蓝桥杯 2023 省 Python B] 保险箱

题目描述

小蓝有一个保险箱，保险箱上共有 $n$ 位数字。

小蓝可以任意调整保险箱上的每个数字，每一次操作可以将其中一位增加 $1$ 或减少 $1$。

当某位原本为 $9$ 或 $0$ 时可能会向前（左边）进位/退位，当最高位（左边第一位）上的数字变化时向前的进位或退位忽略。

例如：

• $00000$ 的第 $5$ 位减 $1$ 变为 $99999$；
• $99999$ 的第 $5$ 位减 $1$ 变为 $99998$；
• $00000$ 的第 $4$ 位减 $1$ 变为 $99990$；
• $97993$ 的第 $4$ 位加 $1$ 变为 $98003$；
• $99909$ 的第 $3$ 位加 $1$ 变为 $00009$。

保险箱上一开始有一个数字 $x$，小蓝希望把它变成 $y$，这样才能打开它，问小蓝最少需要操作的次数。

输入格式

输入的第一行包含一个整数 $n$。

第二行包含一个 $n$ 位整数 $x$。

第三行包含一个 $n$ 位整数 $y$。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

5
12349
54321

输出 #1

11

说明/提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1\le n\le 300$；
• 对于 $60\%$ 的评测用例，$1\le n\le 3000$；
• 对于所有评测用例，$1\le n\le 10^5$，$x,y$ 中仅包含数字 $0$ 至 $9$，可能有前导零。

C++实现

#include <bits/stdc++.h>
using namespace std;

int dp[100005][3], x[100005] = {0}, y[100005] = {0};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	string xx, yy;
	
    cin >> n >> xx >> yy;
    
    for (int i = 1; i <= n; i++){
	 
		x[i] = xx[n - i] - '0'; 
		y[i] = yy[n - i] - '0';
	}
    dp[1][1] = 10 - x[1] + y[1];
    dp[1][2] = 10 - y[1] + x[1];
    dp[1][0] = abs(x[1] - y[1]);
    for (int i = 2; i <= n; i++){
        dp[i][1] = min({dp[i-1][0] + 10 - x[i] + y[i], dp[i-1][1] + 9 - x[i] + y[i], dp[i-1][2] + 11 - x[i] + y[i]});
        dp[i][2] = min({dp[i-1][0] + 10 - y[i] + x[i], dp[i-1][1] + 11 - y[i] + x[i], dp[i-1][2] + 9 - y[i] + x[i]});
        dp[i][0] = min({dp[i-1][0] + abs(x[i] - y[i]), dp[i-1][1] + abs(x[i] + 1 - y[i]), dp[i-1][2] + abs(x[i] - 1 - y[i])});
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2]});
    return 0;
}	

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容