题目分析

我们需要计算区间 $[L, R]$ 内所有数字在 $K$ 进制表示下，将各位数字代表的石子堆合并成一堆的最小代价。每次移动石子的代价是移动的石子数乘以移动的距离。

解题思路

对于每个数字的 $K$ 进制表示，我们需要找到最优的合并位置，使得总移动代价最小。通过数位动态规划结合容斥原理，我们可以高效地计算区间内所有数字的最小代价之和。

算法核心

1. 数位DP：将数字分解为 $K$ 进制数位进行处理
2. 容斥原理：通过计算所有可能合并位置的代价，利用容斥求出真正的最小代价
3. 记忆化搜索：优化状态转移，避免重复计算

完整代码

#include <bits/stdc++.h>

using i64 = long long;

i64 l, r, k, ans, dp[105][10005];
int tot, a[105];

i64 dfs(int u, i64 nw, int id, bool fg) {
    if (!u)
        return std::max(0ll, nw);

    if (nw < 0)
        return 0;

    if (fg && dp[u][nw] != -1)
        return dp[u][nw];

    i64 ans = 0, up = (fg ? k - 1 : a[u]);

    for (int i = 0; i <= up; i++) {
        i64 cost;

        if (id == 1) {
            cost = i * (u - 1);
        } else if (u < id) {
            cost = -1 * i;
        } else {
            cost = i;
        }

        ans += dfs(u - 1, nw + cost, id, fg || (i != up));
    }

    if (fg)
        dp[u][nw] = ans;

    return ans;
}

i64 calc(i64 x) {
    tot = 0;

    while (x) {
        a[++tot] = x % k;
        x /= k;
    }

    memset(dp, -1, sizeof(dp));
    ans = dfs(tot, 0, 1, 0);

    for (int i = 2; i <= tot; i++) {
        memset(dp, -1, sizeof(dp));
        ans -= dfs(tot, 0, i, 0);
    }

    return ans;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);

    std::cin >> l >> r >> k;
    std::cout << calc(r) - calc(l - 1) << '\n';

    return 0;
}

代码说明

• dfs(u, nw, id, fg)：数位DP搜索函数，计算合并到位置id的代价
• calc(x)：计算$[1,x]$区间内所有数字的最小代价之和
• 主函数通过calc(r) - calc(l-1)得到区间$[L,R]$的结果

复杂度分析

• 时间复杂度：$O(\log_K R \times K \times C)$，其中$C$为代价上限
• 空间复杂度：$O(\log_K R \times C)$