Sam的大富翁 题解

题目分析

从 1 出发，每次有两种操作：

1. 使用加法骰子，可以让当前数字增加 1~k；
2. 使用乘法骰子，可以让当前数字变成原来的 p 倍。

要求到达 E 的最少操作次数。

---

1. DP

当 E 比较小时，可以直接设：

$$dp[i]=从1到达i的最少操作次数$$

从 i 出发，可以转移到：

$$i+1,i+2,\cdots,i+k$$

以及：

$$i\times p$$

所以直接枚举即可，复杂度为 O(Ek)。

代码中的 solve(E) 就是这个 DP：

void solve(int E){
    for(int i=1;i<=E;i++) dp[i]=INF;
    dp[1]=0;
    for(int i=1;i<=E;i++){
        for(int j=1;j<=k&&i+j<=E;j++)
            dp[i+j]=min(dp[i+j],dp[i]+1);
        if(i*p<=E)
            dp[i*p]=min(dp[i*p],dp[i]+1);
    }
}

---

2.

当 E 很大时，不能直接 DP。

考虑最后一次使用乘法。假设乘法前到达：

$$q=\lfloor E/p\rfloor$$

那么做一次乘法后：

$$q\rightarrow q\times p$$

由于：

$$E=qp+r$$

其中：

$$r=E\bmod p$$

所以乘法之后还差 r，只需要再进行：

$$\left\lceil\frac r k\right\rceil$$

次加法。

因此，如果采用这种方案，答案就是：

$$f(q)+1+\left\lceil\frac{r}{k}\right\rceil$$

其中 +1 表示最后进行的那一次乘法。

于是可以递归：

int solveb(int E){
    if(E<=100005){
        solve(E);
        return dp[E];
    }
    int q=E/p;
    int r=E%p;
    int need=solveb(q)+1;
    if(r) need+=(r+k-1)/k;
    return need;
}

这里的好处是每次递归都会变成 E/p，所以 E 会快速变小，最多只有 O(log_p E) 层。

---

3. 为什么 q=E/p

这里利用了题目的条件：

$$k<p$$

假设最后一次乘法前到达的是比 E/p 更小的数，例如 q-1。

把它提高到 q，最多只需要一次加法；但是乘法以后：

$$(q-1)p\rightarrow qp$$

增加了 p，而一次加法最多只能增加 k，由于 p>k，因此这样不会让答案变差。

所以最后一次乘法之前可以直接取最大的：

$$q=\lfloor E/p\rfloor$$

---

4. 还要考虑完全不乘

上面的递归方案默认使用了乘法，但有的同学就会说了：欸！直接加法会不会比乘法更优？实际上是不会的,因为$k \le p$， 所以在能出现走p的情况下，肯定是走p的，否则刚刚的式子也能成立

特别地，当 p=1 时，乘法相当于不动，所以直接只考虑加法。

完整代码

#include<bits/stdc++.h>
using namespace std;
const int B = 5000;
const int INF=1e9;
long long  k, p;
#define int long long
int dp[100005];
void solve(int E) {
    
    for(int i=1;i<=E;i++) {
        dp[i]=INF;
    }
    dp[1]=0;
    for(int i = 1; i <= E; i++){
        for(int j = 1; j <= k && i + j <= E; j++) {
            dp[i + j] = min(dp[i + j], dp[i] + 1);
        }
        if(i * p <= E) {
            dp[i * p] = min(dp[i * p], dp[i] +1);
        }   
    }
}
// }
// int solveb(int E){
//     if(E <= 100005){
//         solve(E);
//         return  dp[E];
//     }
//     int need = solveb(E/p);
//     int k1 = E/p;
//     need += (k1 + k - 1) / k + 1;
//     return need;
// }
int solveb(int E){
    if(E<=100004){
        solve(E);
        return dp[E];
    }

    int q=E/p;
    int r=E%p;

    int need=solveb(q);

    need+=1;

    if(r)
        need+=(r+k-1)/k;

    return need;
}
signed main(){
     freopen("dice.in", "r", stdin);
     freopen("dice.out", "w", stdout);
     
    long long E;
    cin >> k >> p >> E;
       if (p == 1) {
        if (E == 1) {
            cout << 0;
            return 0;
        }
        cout << (E - 2) / k + 1;
        return 0;
    }
        cout <<  solveb(E);
    
    return 0;
}

复杂度： E<100005 时为 O(Ek)；E 很大时，每次递归除以 p，复杂度约为 O(log_p E)。