ABC188 F - +1-1x2 题解

原题链接

Description

给定两个数字 \(x\) 和 \(y\) ，以及三种操作，分别可以为 \(x+1\) ，\(x-1\) ， \(x\times2\) , 请问将 \(x\) 变为 \(y\) 的最小操作数。

Solution

可以直接暴力搜，但肯定会重复搜到同个数字，考虑记忆化搜索。

若从 \(x\) 开始操作的话，那么三种操作就都需要搜一次，没有必要的搜索就会变多，可以考虑反着搜，那么我们就可以根据当前数的奇偶，来判读当前数是否直接 \(\times2\) 得到，或者是先 \(+-1\) 后 \(\times2\) 来得到，这样做可以减少很多不必要的搜索。

设 \(f[i]\) 为将 \(y\) 变为 \(i\) 的最小操作数，因为 \(x\) 和 \(y\) 的大小是 \(10^{18}\) 的，所以 \(f[i]\) 要用 \(map\) 开。

对于状态的转移：

初始化 \(f[i]=i-x\)

• 当 \(i\) 为奇数

\(f[i]=min(f[i],f[(i-1)/2]+2)\)

\(f[i]=min(f[i],f[(i+1)/2]+2)\)

• 当 \(i\) 为偶数

\(f[i]=min(f[i],f[i/2]+1)\)

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
#define MAXN 100010
#define INF 0x3f3f3f3f
#define int long long
int Read()
{int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}return x*f;
}
int x,y;
map<int,int> f;
int Dfs(int now)
{if(now==x) return 0;if(now<x) return x-now;if(f[now]) return f[now];f[now]=now-x;if(now%2==0) f[now]=min(f[now],Dfs(now/2)+1);if(now%2==1) f[now]=min(f[now],min(Dfs((now-1)/2)+2,Dfs((now+1)/2)+2));return f[now];
}
signed main()
{x=Read();y=Read();cout<<Dfs(y);return 0;
}