acwing 5408 保险箱

题意

给定n位字符串，可以对每位进行+1/-1的操作，同时产生相应的进位/退位，9999+1将会变为0000，求变成目标串最少的操作次数

思路

这道题一开始还以为是ICPC沈阳的一道题Luggage Lock，但是那道题可以对连续几位同时进行+1/-1，本题只能对一位处理且会产生进位/退位。

正解为状态机dp，表示当前在第位,将要通过方式所需要的最少操作次数，其中方式分别表示：

• 0：不进位也不退位

• 1：退位

• 2：进位

状态转移方程式如下：

$$f_{i,0}=\min {f_{i+1,0}+abs(a-b),f_{i+1,1}+abs(a-1-b),f_{i+1,2}+abs(a+1-b)}\\ f_{i,1}=\min {f_{i+1,0}+a+10-b,f_{i+1,1}+(a-1)+10-b,f_{i+1,2}+(a+1)+10-b}\\ f_{i,2}=\min {f_{i+1,0}+b+10-a,f_{i+1,1}+b+10-(a-1),f_{i+1,2}+b+10-(a+1)}$$

由于某一位的改变只会对他的前面一位产生影响，所以需要倒着进行遍历

不需要考虑第一位的改变对于最后一位的影响，显然第一位进位不会更优

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
int char_to_num(char ch){
    return ch-'0';
}
void solve()
{
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    vector<vector<int>>f(n+2,vector<int>(3));
    int a=char_to_num(s[n-1]),b=char_to_num(t[n-1]);

    f[n-1][0]=fabs(a-b);
    f[n-1][1]=a+10-b;
    f[n-1][2]=b+10-a;
    for(int i=n-2;i>=0;--i){
        int a=char_to_num(s[i]),b=char_to_num(t[i]);
        f[i][0]=min({f[i+1][0]+fabs(a-b),f[i+1][1]+fabs(a-1-b),f[i+1][2]+fabs(a+1-b)});
        f[i][1]=min({f[i+1][0]+a+10-b,f[i+1][1]+a-1+10-b,f[i+1][2]+a+1+10-b});
        f[i][2]=min({f[i+1][0]+b+10-a,f[i+1][1]+b+10-(a-1),f[i+1][2]+b+10-(a+1)});
        
    }
    
    cout<<min({f[0][0],f[0][1],f[0][2]})<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}