杭电多校赛第9场1002 Shortest path

给定一个数字n，每次可以选择一项。

令n = n - 1

令n = n / 2 , if n % 2 == 0

令n = n / 3 , if n % 3 == 0

求最少需要多少步可以让其变成1.

减1操作可以看作是为了除法做准备，连续超过两次减1再除2是不优的，连续超过三次减1再除2也是不优的。

可以根据下一步除2还是除3来分出两个分支。

用搜索表示就是

对于n来说，其可以搜索到的数字是 \(\lfloor\frac{n}{2^a3^b} \rfloor\) , 根据a，b的取值不同可以有\(log^2(n)\)个状态。

即使用记忆化之后，单次查询复杂度是\(log^2(n)\)

#include<unordered_map>
#include<iostream>
using namespace std;

unordered_map<long long , int> Dp;

int Dfs(long long n)
{
    if(n <= 1) return 0;
    if(Dp.count(n)) return Dp[n];
    return Dp[n] = min(Dfs(n / 2) + n % 2 + 1 , Dfs(n / 3) + n % 3 + 1);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    long long n;
    cin >> T;
    while(T--)
    {
        cin >> n , cout << Dfs(n) << '\n';
    }
    return 0;
}