专栏文章

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

zzhanghq2012
P12381题解参与者 12已保存评论 11

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@mipbfdtu
此快照首次捕获于
2025/12/03 09:15
3 个月前
此快照最后确认于
2025/12/03 09:15
3 个月前
查看原文
本蒟蒻的第一篇题解，不喜勿喷
这道题就是一道难度不是特别大的 dp 题

思路

对于每一位都有 33 种可能：
  1. 进位。
  2. 退位。
  3. 不退不进。
建立二维数组 dpi,jdp_{i,j}，其中 ii 表示第几位，jj 表示第几种情况，然后动态规划。
状态转移方程（取最小值）：
  1. 进位：dpi,1=min⁡(dpi−1,0+10−xi+yi,dpi−1,1+9−xi+yi,dpi−1,2+11−xi+yi)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)。
  2. 退位：dpi,2=min⁡(dpi−1,0+10−yi+xi,dpi−1,1+11−yi+xi,dpi−1,2+9−yi+xi)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)。
  3. 不进不退：dpi,0=min⁡(dpi−1,0+∣xi−yi∣,dpi−1,1+∣xi+1−yi∣,dpi−1,2+∣xi−1−yi∣)dp_{i,0} = \min(dp_{i-1,0} + |x_i - y_i|, dp_{i-1,1} + |x_i + 1 - y_i|, dp_{i-1,2} + |x_i - 1 - y_i|)。

AC代码

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

评论

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

正在加载评论...