2021年区域赛ICPC沈阳站J-Luggage Lock（代码简洁）

题意：将给一个4位的锁转到另一个四位的锁，可以一次转动多个连续的锁+1或者-1，问多少次可以转成目标锁

输入

6
1234 2345
1234 0123
1234 2267
1234 3401
1234 1344
1234 2468

输出

1
1
4
5
1
4

总体思路：

这题我的做法就是分成两个题：

1.一个是给一个正数数组，比如4,5,6,2，每次可以下降一个连续的区间，需要最少多少次。

难一点，如果其中有负数，可以连续上升和下降又怎么算：4,-2,5的答案是11。

2.然后计算出4位的差，比如4562到5671的差就是-1，-1，-1，1，上面问题只要解决了，带入该数组可以出来答案。

但是4562到5671还可以9，-1，-1，1，每位加还是减就有2^4次种情况，搜索列举出这16个数组求出最小答案即可。

具体解法：

第1个问题：

有原题的：[NOIP2018 提高组] 铺设道路 - 洛谷

对于全是正数的数组很简单：答案就是sum

for(int i=1;i<=n;i++)
    if(a[i-1]<a[i])
        sum+=a[i]-a[i-1];

对于有负数的数组，可以在正数和负数中间多加一个0，负数变为其绝对值

1,2,-1,-2,3  ->  1,2,0,1,2,0,3

当然这只是便于理解的做法，加上0太麻烦，可以直接算，其实也就是在中间加上0后的计算：

void solve(){
    int sum=0;
    for(int i=1;i<=4;i++){
        if(ans[i-1]*ans[i]<0) sum+=abs(ans[i]);      //ans是长度为5的数组,ans[0]=0,后面4个是有效的
        else if(abs(ans[i])>abs(ans[i-1])) sum+=abs(ans[i])-abs(ans[i-1]);
    }
    minn=min(minn,sum);
}

第2个问题：

就不算问题了 ，但是指明一下说的ans数组是输入数据的差数组

如果可知该位ans[i]<0，那么再+10，如果ans[i]>=0，那么再-10，列举出16种数组即可

因为第1个问题时间复杂度O（n）解决了，3^4的枚举也可以的：

void dfs(int d){
    if(d==5){
        solve();        //数组ans产生一个结果
        return;
    }
    ans[d]=x[d-1]-y[d-1];       //取差
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]+10;        //该位+10
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]-10;        //该位-10
    dfs(d+1);
}

代码：

#include<bits/stdc++.h>
using namespace std;
#define fo(a) for(int i=0;i<a;i++)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define M 1000005
int T,minn;
string s;
vector<int>x,y;
vector<int>ans(5);
void solve(){
    int sum=0;
    for(int i=1;i<=4;i++){
        if(ans[i-1]*ans[i]<0) sum+=abs(ans[i]);
        else if(abs(ans[i])>abs(ans[i-1])) sum+=abs(ans[i])-abs(ans[i-1]);
    }
    minn=min(minn,sum);
}
void dfs(int d){
    if(d==5){
        solve();
        return;
    }
    ans[d]=x[d-1]-y[d-1];       //取差
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]+10;        //该位+10
    dfs(d+1);
    ans[d]=x[d-1]-y[d-1]-10;        //该位-10
    dfs(d+1);
}
signed main(){
    cin>>T;
    while(T--){
        minn=1e9;
        x.clear();y.clear();
        cin>>s;
        fo(4) x.push_back(s[i]-'0');
        cin>>s;
        fo(4) y.push_back(s[i]-'0');
        dfs(1);
        cout<<minn<<'\n';
    }
    return 0;
}