题目描述
难度分:$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]$。
状态转移
分为两种情况:
- 如果$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}])$。
- 否则就只有减$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)