AtCoder Beginner Contest 188 F- +1-1x2 记忆化搜索
传送门： https://atcoder.jp/contests/abc188/tasks/abc188_f
题意
在 只 能 在 + 1 − 1 和 ∗ 2 三 种 操 作 的 情 况 下 ， 如 果 将 X 变 为 Y ? 在只能在+1-1和*2三种操作的情况下，如果将X变为Y? 在只能在+1−1和∗2三种操作的情况下，如果将X变为Y?
思路
因 为 每 次 操 作 都 会 经 过 三 次 选 择 ， 是 + 1 呢 还 是 − 1 呢 还 是 ∗ 2 呢 ？ 因为每次操作都会经过三次选择，是+1呢还是-1呢还是*2呢？ 因为每次操作都会经过三次选择，是+1呢还是−1呢还是∗2呢？
因 为 这 个 转 移 是 从 后 往 前 转 移 ， 所 以 是 将 Y 如 何 变 为 X 即 可 ， 只 不 过 ∗ 2 变 为 / 2 而 已 。 因为这个转移是从后往前转移，所以是将Y如何变为X即可，只不过*2变为/2而已。 因为这个转移是从后往前转移，所以是将Y如何变为X即可，只不过∗2变为/2而已。
所 以 有 一 下 转 移 方 案 ： ( ) − 1 表 示 逆 过 程 所以有一下转移方案：()^{-1}表示逆过程 所以有一下转移方案：()−1表示逆过程
在 转 移 到 为 n 时 在转移到为n时 在转移到为n时
- 当 n < = x 时 ， r e t u r n n − x （ ( − 1 ) − 1 转 移 ） 当n<=x时，return \;\;n-x（(-1)^{-1}转移） 当n<=x时，returnn−x（(−1)−1转移）
- 当 n 为 任 意 数 时 ， r e t u r n x − n （ ( + 1 ) − 1 转 移 ） 当n为任意数时，return \;\;x-n（(+1)^{-1}转移） 当n为任意数时，returnx−n（(+1)−1转移）
- 当 n 为 偶 数 时 ， r e t u r n D F S ( n / 2 ) + 1 （ ( ∗ 2 ) − 1 转 移 ） 当n为偶数时，return \;\;DFS(n / 2)+1（(*2)^{-1}转移） 当n为偶数时，returnDFS(n/2)+1（(∗2)−1转移）
- 当 n 为 奇 数 时 ， r e t u r n D F S ( ( n − 1 ) / 2 ) + 2 （ + 1 ∗ 2 ） − 1 转 移 当n为奇数时，return \;\;DFS((n-1) / 2)+2（+1*2）^{-1}转移 当n为奇数时，returnDFS((n−1)/2)+2（+1∗2）−1转移
-
当
n
为
奇
数
时
，
r
e
t
u
r
n
D
F
S
(
(
n
+
1
)
/
2
)
+
2
（
−
1
∗
2
）
−
1
转
移
当n为奇数时，return \;\;DFS((n+1)/2)+2（-1*2）^{-1}转移
当n为奇数时，returnDFS((n+1)/2)+2（−1∗2）−1转移
最后取min即可。
看 到 上 面 有 很 多 状 态 转 移 ， 所 以 我 们 可 以 在 D F S 过 程 中 记 忆 化 。 看到上面有很多状态转移，所以我们可以在DFS过程中记忆化。 看到上面有很多状态转移，所以我们可以在DFS过程中记忆化。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll X, Y;
map<ll, ll> dp;
ll DFS(ll n) {
if(X >= n) return X - n; // 直接-1转移
if(dp[n]) return dp[n]; // 记忆化搜索
ll ans = n - X; // 直接+1转移
ans = min(ans, DFS(n / 2) + 1 + n % 2); // 偶数直接*2 或者 先+1在*2
if(n % 2) ans = min(ans, DFS(n / 2 + 1) + 2); // 先-1在*2
return dp[n] = ans;
}
void solve() {
cin >> X >> Y;
cout << DFS(Y) << endl;
}
signed main() {
solve();
}