AcWing:5408. 保险箱

小蓝有一个保险箱，保险箱上共有?n?位数字。

小蓝可以任意调整保险箱上的每个数字，每一次操作可以将其中一位增加?1?或减少?1。

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

例如:

00000?的第?5?位减?1?变为?99999；

99999?的第?5?位减?1?变为?99998；

00000?的第?4?位减?1?变为?99990；

97993?的第?4?位加?1?变为?98003；

99909?的第?3?位加?1?变为?00009。

保险箱上一开始有一个数字?x，小蓝希望把它变成?y，这样才能打开它，问小蓝最少需要操作的次数。

输入格式

输入的第一行包含一个整数?n。

第二行包含一个?n?位整数?x。

第三行包含一个?n?位整数?y。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于?30%?的评测用例，1≤n≤300；
对于?60%?的评测用例，1≤n≤3000；
对于所有评测用例，1≤n≤10^5，x,y?中仅包含数字?0?至?9，可能有前导零。

输入样例：

5
12349
54321

输出样例：

11

对样例的解释:

1 2 3 4 9　－＞　5 4 3 2 1

= + 40000 + 2000 + 000 - 20 -? 8

= +40000 + 2000 + 000 - 30 + 2

答案 = ４＋２＋０＋３＋２＝１１

?讲讲思路:

对于保险箱上的数字,要么加一,要么减一,要么不动?三者取其一

也就是三个状态

那么加一和减一的操作相当于进位与退位

其操作只会影响前面的数,故我们倒序进行DP

对进位,退位,与不动三个操作进行分析,最后取最小值即可

以下是AC代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

/* 定义 */
const int N = 1e5 + 10;
int n;
int a[N] , b[N]; 
int f[N][3]; 

int main()
{
    /* 正常读入 */
    cin >> n;
    string s1 , s2;
    cin >> s1 >> s2;
    
    /* 把各个数位提取放置数组中 */
    for (int i = 0; i < n; i ++ ) a[i] = s1[i] - '0' , b[i] = s2[i] - '0';
    
    /* dp的初始化 */
    f[n - 1][0] = abs(a[n - 1] - b[n - 1]); // 不进不退
    f[n - 1][1] = 10 - a[n - 1] + b[n - 1]; // 进位
    f[n - 1][2] = 10 + a[n - 1] - b[n - 1]; // 退位
    
    
    for (int i = n - 2; i > -1; i -- )
    {
        /* 不进不退 */
        f[i][0] = f[i + 1][0] + abs(a[i] - b[i]); // 前面不进不退,直接加
        f[i][0] = min(f[i][0], f[i + 1][1] + abs(a[i] + 1 - b[i])); // 前面进位,比一下进位与不动的代价 
        f[i][0] = min(f[i][0], f[i + 1][2] + abs(a[i] - 1 - b[i])); // 前面退位,比一下退为与不动的代价

        /* 进位 */
        f[i][1] = f[i + 1][0] + (10 - a[i] + b[i]); 
        f[i][1] = min(f[i][1], f[i + 1][1] + (10 - a[i] + b[i] - 1)); 
        f[i][1] = min(f[i][1], f[i + 1][2] + (10 - a[i] + b[i] + 1)); 

        /* 退位 */
        f[i][2] = f[i + 1][0] + (a[i] - b[i] + 10); 
        f[i][2] = min(f[i][2], f[i + 1][1] + (a[i] - b[i] + 10 + 1)); 
        f[i][2] = min(f[i][2], f[i + 1][2] + (a[i] - b[i] + 10 - 1));

    }
    
    cout << min(min(f[0][0] , f[0][1]) , f[0][2]); // 输出三者取最小
    
    return 0;
}