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