AtCoder Beginner Contest 188 F- +1-1x2 记忆化搜索

传送门：https://atcoder.jp/contests/abc188/tasks/abc188_f

题意

在只能在+1-1和*2三种操作的情况下，如果将X变为Y?

思路

因为每次操作都会经过三次选择，是+1呢还是-1呢还是*2呢？

因为这个转移是从后往前转移，所以是将Y如何变为X即可，只不过*2变为/2而已。

所以有一下转移方案：$()^{-1}$表示逆过程

在转移到为n时

  • 当n<=x时，$return \;\;n-x((-1)^{-1}$转移）
  • 当n为任意数时，$return \;\;x-n（(+1)^{-1}$转移）
  • 当n为偶数时，$return \;\;DFS(n / 2)+1((*2)^{-1}$转移)
  • 当n为奇数时，$return \;\;DFS((n-1) / 2)+2(+1*2)^{-1}$转移
  • 当n为奇数时，$return \;\;DFS((n+1)/2)+2(-1*2)^{-1}$转移 最后取min即可。

看到上面有很多状态转移，所以我们可以在DFS过程中记忆化。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
##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();
}