题目描述

方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧,位置在$i$的人面前的第$j$堆的石子的数量,刚好是$i$写成$K$进制后的第$j$位。

现在方伯伯要玩一个游戏,商场会给方伯伯两个整数$L,R$。方伯伯要把位置在$[L,R]$中的每个人的石子都合并成一堆石子。每次操作,他可以选择一个人面前的两堆石子,将其中的一堆中的某些石子移动到另一堆,代价是移动的石子数量$\times$移动的距离。商场承诺,方伯伯只要完成任务,就给他一些椰子,代价越小,给他的椰子越多。所以方伯伯很着急,想请你告诉他最少的代价是多少。

输入格式

输入仅有一行,包含三个用空格分隔的整数$L$,$R$,$K$,表示商场给方伯伯的两个整数,以及进制数。

输出格式

输出仅有一行,包含一个整数,表示最少的代价。

题解

考虑用$1\sim R$的答案减掉$1\sim L-1$的答案,即$\operatorname{solve}(R) - \operatorname{solve}(L-1)$。

考虑$\operatorname{solve}(n)$,先计算把每个人的石子都全部合并到第$1$堆所需的代价

这个是可以通过一次数位dp解决的

1
2
3
4
5
6
7
8
9
10
11
ll dfs1(ll d, ll sum, ll lim) {
if (!d) return sum;
if (!lim && ~f[d][sum]) return f[d][sum];
ll ret = 0; int mx = lim ? a[d] : k-1;
for (ll i = 0; i <= mx; i++) {
ret += dfs1(d-1, sum + i * (d - 1), lim & (i == mx));
//第d位有i个石子要移动到第1位
}
if (!lim) f[d][sum] = ret;
return ret;
}

注意到这样一个性质:对于一个人$x$,假设他把所有石子最终全部移到第$k$位,我们把$k$叫做$x$的集合点,这样移动的代价是$f_x(k)$,那么$f_x$一定是一个单谷函数

不妨把$x$的最优集合点叫做$p_x$

所以我们可以执行这样的操作:

for i=2~n,每次把所有 “集合点在$i$时比在$i-1$时更优 (即$f_x(i-1)>f_x(i)$)” 的那些$x$的集合点全部从$i-1$变为$i$,也就是说让答案减去$f_x(i-1)-f_x(i)$

这样一来,由于$f_x$是单谷函数,那么一个人$x$一定在$i=2\sim p_x$的时候集合点被移动,那么$x$的最终代价就会是$f_x(p_x)$,所以这个做法是正确的

然后考虑如何进行这个”挪动集合点”的操作 其实和上面的那个计算集合点全为1的数位dp区别不大

1
2
3
4
5
6
7
8
9
10
ll dfs2(ll d, ll sum, ll p, ll lim) {
if (!d) return max(0ll, sum); //如果sum<0则说明不把集合点从p-1挪到p比较优
if (!lim && ~f[d][sum]) return f[d][sum];
ll ret = 0; int mx = lim ? a[d] : k-1;
for (ll i = 0; i <= mx; i++) {
ret += dfs2(d-1, sum + (d < p ? -i : i), p, lim & (i == mx));
}
if (!lim) f[d][sum] = ret;
return ret;
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll k, len, a[60];
ll L, R, f[60][5005];

ll dfs1(ll d, ll sum, ll lim) {
if (!d) return sum;
if (!lim && ~f[d][sum]) return f[d][sum];
ll ret = 0; int mx = lim ? a[d] : k-1;
for (ll i = 0; i <= mx; i++) {
ret += dfs1(d-1, sum + i * (d - 1), lim & (i == mx));
}
if (!lim) f[d][sum] = ret;
return ret;
}

ll dfs2(ll d, ll sum, ll p, ll lim) {
if (!d) return max(0ll, sum);
if (!lim && ~f[d][sum]) return f[d][sum];
ll ret = 0; int mx = lim ? a[d] : k-1;
for (ll i = 0; i <= mx; i++) {
ret += dfs2(d-1, sum + (d < p ? -i : i), p, lim & (i == mx));
}
if (!lim) f[d][sum] = ret;
return ret;
}

ll solve(ll n) {
len = 0;
ll tmp = n;
while (tmp) {
a[++len] = tmp % k;
tmp /= k;
}
memset(f, -1, sizeof(f));
ll ret = dfs1(len, 0, 1);
for (ll i = 2; i <= len; i++) {
memset(f, -1, sizeof(f));
ret -= dfs2(len, 0, i, 1);
}
return ret;
}

int main() {
scanf("%lld %lld %lld", &L, &R, &k);
printf("%lld\n", solve(R) - solve(L-1));
return 0;
}

评论