#P3598. [Scoi2014]方伯伯的商场之旅

    ID: 2805 传统题 3000ms 64MiB 尝试: 612 已通过: 294 难度: 7 上传者: 标签>难度分类提高+/省选-组合数学贡献法贪心中位数最小化绝对偏差和动态规划数位 DP上界限制状态状态维度消除滚动数组CF2300By

[Scoi2014]方伯伯的商场之旅

[SCOI2014] 方伯伯的商场之旅

题目描述

方伯伯去参加商场举办的游戏。商场的工作人员按位置编号排成一行。位置 ii 的人面前有若干堆石子,分别对应 ii 的 KK 进制表示的各个数位。每堆的石子数等于该数位的数字,石子堆依数位顺序排列。

对每位编号在闭区间 [L,R][L,R] 内的工作人员,都要把他面前的石子集中到同一堆。一次操作可将某一堆中的若干颗石子移动到同一个人面前的另一堆。代价等于移动的石子数乘以两堆之间的距离,距离按堆的位置编号之差的绝对值计算。

例如在十进制下,位置 1231212312 的人面前各堆有 1,2,3,1,21,2,3,1,2 颗石子。集中到第三堆的代价为 1⋅2+2⋅1+3⋅0+1⋅1+2⋅2=91\cdot2+2\cdot1+3\cdot0+1\cdot1+2\cdot2=9,这是他的最小代价。

商场给出 L,RL,R,并承诺方伯伯完成任务后,代价越小就送他越多的椰子。求所有这些工作人员的最小总代价。

输入格式

一行三个整数 L,R,KL,R,K,分别表示起始位置、结束位置和进制。

输出格式

输出一行一个整数,表示最小总代价。

样例

3 8 3
5

数据范围

对于 100%100\% 的数据,1≤L≤R≤1015,2≤K≤201 \le L \le R \le 10^{15}, 2 \le K \le 20。