P12381 题解

Helenty · 2025-04-29 22:11:05 · 题解

依题意得，每一次操作可以将其中一位数字 +1 或 -1。

注意：

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

显然的一道二维线性 DP 题。主要是要理解三个状态：不进不退、进位和退位。

第一维存目前到第几个了，第二位存当前的状态，即不进不退或进位或退位。

C++ 代码如下：

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

int n, dp[100005][3], x[100005] = {0}, y[100005] = {0};
char x_str[100005], y_str[100005];

int main()
{
    cin >> n >> x_str >> y_str;
    for (int i = 1; i <= n; ++i) x[i] = x_str[n - i] - '0', y[i] = y_str[n - i] - '0';

    dp[1][0] = abs(x[1] - y[1]);  // 不进不退
    dp[1][1] = 10 - x[1] + y[1];  // 进位
    dp[1][2] = 10 - y[1] + x[1];  // 退位

    for (int i = 2; i <= n; ++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])});

        // 进位
        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]});
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << endl;
    return 0;
}

Python 代码如下：

n = int(input())
x = [0] + list(map(int, list(input())))[::-1]
y = [0] + list(map(int, list(input())))[::-1]
dp = [[0]*3 for _ in range(n+1)]
# 不进不退
dp[1][0] = abs(x[1]-y[1])
# 进位
dp[1][1] = 10 - x[1] + y[1]
# 退位
dp[1][2] = 10 - y[1] + x[1]

for i in range(2, n+1):
    # 不进不退
    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]))
    # 进位
    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])
print(min(dp[n][0],dp[n][1],dp[n][2]))