题解：P15731 [JAG 2024 Summer Camp #2] Convenient Banknotes

fzitb7912 · 2026-11-10 21:09:37 · 题解

分析

不妨设 k = 3。记 X_2 = a,X_3 = a\cdot b。考虑计算 A 日元所需最小纸币张数。

显然就是 \lfloor\frac{A}{a\cdot b}\rfloor + \lfloor\frac{A\bmod (a\cdot b)}{a}\rfloor + A\bmod a。设 A = C\cdot a\cdot b + B。那么原式等于：

拓展到 k \ne 3。记 D_i = \frac{X_{i+1}}{X_{i}}。

设 S 为 A 日元所需最小纸币张数，那么 S 可以这么算出来：

1. 枚举 i = 1\dots k-1。将 S 增加 A\bmod D_{i}，并将 A 变成 \lfloor\frac{A}{D_i}\rfloor。

2. 在枚举完 i 后，将 S 增加 A。

考虑 DP。

定义状态函数 f(A,B,C) 为如果要表示出 A,B,C，所需的最小代价。枚举 D \ge 2，分情况讨论：

1. 是情况 1。代价 (A\bmod D) + (B\bmod D)+(C\bmod D) + f(\lfloor\frac{A}{D}\rfloor,\lfloor\frac{B}{D}\rfloor,\lfloor\frac{C}{D}\rfloor)。
2. 是情况 2。代价 A+B+C。

对于情况 1 用整除分块枚举即可。

时间复杂度 O(V^{\frac{3}{4}})。

代码

unordered_map<int, int> f;

il int dfs(int a, int b, int c){
    if(!(a + b + c)) return 0;
    int Hs = a * 1000000000 + b * 1000000 + c;
    if(f.count(Hs)) return f[Hs];
    int spd = a + b + c;
    for(re int d = 2; d <= max({a, b, c}); ){
        int r = max({a, b, c});
        if(a >= d) r = min(r, a / (a / d));
        if(b >= d) r = min(r, b / (b / d));
        if(c >= d) r = min(r, c / (c / d));
        spd = min(spd, a + b + c - r * (a / d + b / d + c / d) + dfs(a / d, b / d, c / d));
        d = r + 1;
    }
    return f[Hs] = spd;
}

il void solve(){ 
    int a = rd, b = rd, c = rd;
    cout << dfs(a, b, c) << "\n";
    return ;
}