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

· · 题解

本蒟蒻的第一篇题解，不喜勿喷

这道题就是一道难度不是特别大的 dp 题

思路

对于每一位都有 3 种可能：

  1. 进位。
  2. 退位。

  3. 不退不进。

    建立二维数组 dp_{i,j}，其中 i 表示第几位，j 表示第几种情况，然后动态规划。

状态转移方程（取最小值）：

  1. 进位：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. 退位：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. 不进不退：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代码

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