2024寒假每日一题全部题解传送门>>

分析题目发现每变动一位数字，只会影响左边的一个数。如果此时该位的数没有发生进位的话，左边的一个数就不会发生变动的；如果当前该位的数是通过加法进位的话，那么左边的一位数字就会加1；如果当前该位的数是通过减法进位的话，那么左边的一位数字就会减1。所以发现当前一位数字是否发生变动是取决于后一位数字的变动，所以定义三种状态：1.右边的数字没有发生进位 2.右边数字通过加法发生了进位 3.右边的数字通过减法发生了进位。用$f[i][0]$、$f[i][1]$和$f[i][2]$分别表示当前位没有发生进位、当前位通过加法发生进位和当前位通过减法发生进位需要操作的最少次数。接下来关键之处就是状态计算了，由于操作当前位并不影响右边的数，所以从右向左进行状态计算（用$x$表示第一个字符串当前位的数字，用$y$表示第二个字符串当前位的数字）：
1. 当前位的数没有发生进位$f[i][0]$：
（1）如果右边的数操作完了之后当前位没有发生改变，那么：
当前位不进位需要操作的次数即为：$f[i][0]=f[i+1][0]+abs(x-y)$。
（2）如果右边的数操作完了之后当前位增大了一位，那么：
当前位不进位需要操作的次数即为：$f[i][0]=f[i+1][1]+abs(x+1-y)$。
（3）如果右边的数操作完了之后当前位减小了一位，那么：
当前位不进位需要操作的次数即为：$f[i][0]=f[i+1][2]+abs(x-1-y)$。
综上：$f[i][0]=min(f[i+1][0]+abs(x-y),f[i+1][1]+abs(x+1-y),f[i+1][2]+abs($$x-1-y))$。
2. 当前位的数通过加法进位$f[i][1]$：
（1）如果右边的数操作完了之后当前位没有发生改变，那么：
当前位通过加法进位需要操作的次数即为：$f[i][1]=f[i+1][0]+abs(y-x+10)$。
（2）如果右边的数操作完了之后当前位增大了一位，那么：
当前位通过加法进位需要操作的次数即为：$f[i][1]=f[i+1][1]+abs(y-(x+1)+10)$。
（3）如果右边的数操作完了之后当前位减小了一位，那么：
当前位通过加法进位需要操作的次数即为：$f[i][1]=f[i+1][2]+abs(y-(x-1)+10)$。
综上：$f[i][1]=min(f[i+1][0]+abs(y-x+10),f[i+1][1]+abs(y-(x+1)+10),f[i+1]$$[2]+abs(y-(x-1)+10))$。
3. 当前位的数通过减法进位$f[i][2]$：
（1）如果右边的数操作完了之后当前位没有发生改变，那么：
当前位通过减法进位需要操作的次数即为：$f[i][2]=f[i+1][0]+abs(x-y+10)$。
（2）如果右边的数操作完了之后当前位增大了一位，那么：
当前位通过减法进位需要操作的次数即为：$f[i][2]=f[i+1][1]+abs((x+1)-y+10)$。
（3）如果右边的数操作完了之后当前位减小了一位，那么：
当前位通过减法进位需要操作的次数即为：$f[i][2]=f[i+1][2]+abs((x-1)-y+10)$。
综上：$f[i][2]=min(f[i+1][0]+abs(x-y+10),f[i+1][1]+abs((x+1)-y+10),f[i+1]$$[2]+abs((x-1)-y+10))$。

最终答案即为$min(f[1][0],f[1][1],f[1][2])$。

C++代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
char s1[N], s2[N];
int f[N][3];
int n;

int get(char c)
{
    return c - '0';
}

int main()
{
    scanf("%d%s%s", &n, s1 + 1, s2 + 1);

    f[n][0] = abs(get(s1[n]) - get(s2[n]));
    f[n][1] = get(s2[n]) - get(s1[n]) + 10;
    f[n][2] = get(s1[n]) - get(s2[n]) + 10;
    for(int i = n - 1; i; i --)
    {
        int x = get(s1[i]), y = get(s2[i]);

        f[i][0] = f[i + 1][0] + abs(x - y);
        f[i][0] = min(f[i][0], f[i + 1][1] + abs(x + 1 - y));
        f[i][0] = min(f[i][0], f[i + 1][2] + abs(x - 1 - y));

        f[i][1] = f[i + 1][0] + y - x + 10;
        f[i][1] = min(f[i][1], f[i + 1][1] + y - x + 9);
        f[i][1] = min(f[i][1], f[i + 1][2] + y - x + 11);

        f[i][2] = f[i + 1][0] + x - y + 10;
        f[i][2] = min(f[i][2], f[i + 1][1] + x - y + 11);
        f[i][2] = min(f[i][2], f[i + 1][2] + x - y + 9);
    }

    printf("%d", min({f[1][0], f[1][1], f[1][2]}));
    return 0;
}