自动搬运

查看原文

来自洛谷，原作者为

	zhanghq2012 做文明事,讲文明语,当文明人,走文明路,传文明风,建文明城,行文明礼,树文明德,扬文明志,创文明业,护文明景,享文明福, 守文明规,践文明行,育文明心,展文明貌,兴文明事,筑文明梦;文爱明，明爱文，文明幸福一家人，世界文明永流传

搬运于2025-08-24 23:15:06，当前版本为作者最后更新于2025-05-13 15:22:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

这道题就是一道难度不是特别大的 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;
}