题目描述

难度分:$1400$

输入$n$，$k$，$a$，$b$$(1 \leq n,k,a,b \leq 2 \times 10^9)$。

有两种操作：

• 花费$a$，把$n$减一。
• 如果$n$是$k$的倍数，花费$b$，把$n$变成$\frac{n}{k}$。

输出把$n$变成$1$的最小总花费。

输入样例$1$

9
2
3
1

输出样例$1$

6

输入样例$2$

5
5
2
20

输出样例$2$

8

输入样例$3$

19
3
4
2

输出样例$3$

12

算法

记忆化搜索

首先我们过滤一个情况，如果$k=1$，肯定不会选择除法操作，因为$\frac{n}{k}=n$，没有任何意义。所以答案就是将$n$每次减$1$得到$1$的代价，为$(n-1)a$。

状态定义

$dp[rest]$表示将$rest$变为$1$的最小代价，按这个定义，答案就应该是$dp[n]$。

状态转移

分为两种情况：

1. 如果$rest$是$k$的倍数，要么通过减$1$的方式让$n$变成$\frac{rest}{k}$，要么通过除以$k$的方式让$rest$变成$\frac{rest}{k}$。状态转移方程为$dp[rest]=min((rest-\frac{rest}{k})a+dp[\frac{rest}{k}],b+dp[\frac{rest}{k}])$。
2. 否则就只有减$1$操作，如果$rest \leq k$，就减去$k-1$变成$1$。否则减去余数$rest \% k$，让$rest$变成$k$的倍数了再做下一步决策。

复杂度分析

时间复杂度

单次转移的时间复杂度是$O(1)$的，虽然在DP的过程中会存在减法操作，但是经过一次减法操作后立马就会使$rest$变成$k$的倍数，这样就可以进行除法操作，状态数量应该是$O(log_kn)$级别。因此，整个算法的时间复杂度为$O(log_kn)$。

空间复杂度

额外空间复杂度就是DP过程中状态的存储消耗，为$O(log_kn)$。

$python$代码

from functools import lru_cache

n = int(input())
k = int(input())
a = int(input())
b = int(input())
if k == 1:
    print((n - 1)*a)
    exit(0)

inf = int(1e18)

@lru_cache(None)
def dfs(rest: int) -> int:
    if rest == 1:
        return 0
    res = inf
    if rest % k == 0:
        res = min(res, min(a*(rest - rest//k) + dfs(rest//k), b + dfs(rest//k)))
    else:
        r = rest % k
        if rest > k:
            res = min(res, a*r + dfs(rest - r))
        else:
            res = min(res, (rest - 1)*a)
    return res

ans = dfs(n)
dfs.cache_clear()
print(ans)