题目描述
小蓝有一个保险箱,保险箱上共有n位数字。
小蓝可以任意调整保险箱上的每个数字,每一次操作可以将其中一位增加1或减少 1。
当某位原本为 9或 0时可能会向前(左边)进位/退位,当最高位(左边第一位)上的数字变化时向前的进位或退位忽略。
例如:
00000的第5位减1变为 99999;
99999的第5位减1变为 99998;
99909的第3位加1变为 00009。
保险箱上一开始有一个数字x,小蓝希望把它变成y,这样才能打开它,问小蓝最少需要操作的次数。
样例
输入样例:
5
12349
54321
输出样例:
11
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n;
int x[N], y[N];
int f[N][3];
string a, b;
/*
>>参考题解中某大佬的思路,这里顺便记录一下我个人的理解,也算加深印象了...>_<;
>>状态集合用f[N][3]维护;
>>状态表示:f[i][0]表示i+1~n位已经匹配完成,对当前第i位数进行匹配,且进行若干次操作匹配成功后,该位既没有进位也没有借位的所有方案;
f[i][1]表示i+1~n位已经匹配完成,对当前第i位数进行匹配,且进行若干次操作匹配成功后,一定突破上限而产生进位的所有方案;
f[i][2]表示i+1~n位已经匹配完成,对当前第i位数进行匹配,且进行若干次操作匹配成功后,一定突破下限而产生借位的所有方案;
>>状态属性:切题意,那就是每种方案中所花费操作最少的方案的操作次数;
>>状态计算:
·首先大家可以先看y总视频,搞清楚为啥选择从后(个位)向前(高位)遍历会更方便,在这就不说了...
·既然从后向前遍历,那么依据经验,对于当前i位的计算一定是需要后面的i+1位状态得来的;
·这里我以计算f[i][0]过程为例讲一下:
->f[i][0]就表示我对于当前第i位的数,要想让x[i]和y[i]匹配,不管i+1位是怎样的,这次匹配策略都是只取x[i]
和y[i]的差绝对值(即:abs(x[i]-y[i])),就是如果y[i]>x[i],那就增加到y[i],如果y[i]<x[i],那就
减小到y[i];
->当然,i+1位的状态是会影响到当前i位的操作的,其实这一点也容易考虑:
f[i+1][0] + abs(x[i]-y[i])——i+1位都无进位借位,那轮到当前i位匹配时,x[i]没变化,所以直接
加上差绝对值即可;
f[i+1][1] + abs(x[i]+1-y[i])——i+1位有进位,那轮到当前i位匹配时,x[i]要先加上1,再加上~;
f[i+1][2] + abs(x[i]-1-y[i])——i+1位有借位,那轮到当前i位匹配时,x[i]要先减去1,再加上~;
->小结:f[i][0]就是考虑了i+1位的三种情况,以及对第i位一直采取差绝对值的匹配策略的方案集合;
·弄懂f[i][0]这个状态集合怎么计算的,剩下f[i][1]和f[i][2]其实都好理解了,这里我就写一下小结:
->小结1:f[i][1]就是考虑了i+1位的三种情况,以及对第i位一直采取突破上限再匹配的匹配策略的方案集合;
->小结2:f[i][2]就是考虑了i+1位的三种情况,以及对第i位一直采取突破下限再匹配的匹配策略的方案集合;
>>代码和思路都不是我本人想出来的,我只是看了别人的题解后自己感受颇深,然后想分享一下自己的对他人思路的个人理解...
*/
int main() {
cin >> n;
cin >> a >> b;
for (int i = 0; i < n; i++) {
x[i] = a[i] - '0';
y[i] = b[i] - '0';
}
memset(f, 0x3f, sizeof f);
f[n - 1][0] = abs(x[n - 1] - y[n - 1]);
f[n - 1][1] = abs(y[n - 1] + 10 - x[n - 1]);
f[n - 1][2] = abs(x[n - 1] + 10 - y[n - 1]);
for (int i = n - 2; i >= 0; i--) {
f[i][0] = min(
{
f[i + 1][0] + abs(x[i] - y[i]),
f[i + 1][1] + abs(x[i] + 1 - y[i]),
f[i + 1][2] + abs(x[i] - 1 - y[i]),
});
f[i][1] = min(
{
f[i + 1][0] + abs(y[i] + 10 - x[i]),
f[i + 1][1] + abs(y[i] + 10 - (x[i] + 1)),
f[i + 1][2] + abs(y[i] + 10 - (x[i] - 1))
});
f[i][2] = min(
{
f[i + 1][0] + abs(x[i] + 10 - y[i]),
f[i + 1][1] + abs(x[i] + 1 + 10 - y[i]),
f[i + 1][2] + abs(x[i] - 1 + 10 - y[i])
});
}
/*
下面是当时自己尝试做的,傻傻的以为利用贪心可以,实际是不行滴...
*/
// int ans = 0, bit = 0;
// for (int i = n - 1; i >= 0; i--) {
// int flag = 0;
// if (bit == -1) {
// if (x[i] == 0) x[i] = 9;
// else x[i]--;
// }
// else if (bit == 1) {
// if (x[i] == 9) x[i] = 0;
// else x[i]++;
// }
// if (x[i] > y[i]) {
// if (x[i] - y[i] < y[i] + 10 - x[i]) ans += (x[i] - y[i]);
// else {
// ans += (y[i] + 10 - x[i]);
// bit += 1;
// flag = 1;
// }
// x[i] = y[i];
// }
// else if (x[i] < y[i]) {
// if (y[i] - x[i] < x[i] + 10 - y[i]) ans += (y[i] - x[i]);
// else {
// ans += (x[i] + 10 - y[i]);
// bit -= 1;
// flag = 1;
// }
// x[i] = y[i];
// }
// if (flag == 0) bit = 0;
// }
//cout << ans;
cout << min({f[0][0], f[0][1], f[0][2]});
return 0;
}