ABC188 F - +1-1x2 题解

zhln / 2024-09-26 / 原文

原题链接

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;
}