题目描述
方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧，位置在$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));
}
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);
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;
}
|
