数位DP三大核心思想：1.区间求和转化为前缀和相减 2.逐位确定 3.不对拍基本要完
对于这道题,我们首先考虑单个数字的最优解是什么.找一下规律发现应当把所有数字集中在原先数字总和一半的地方.
不妨想象一个直线上有n个点,找一个点到n个点距离之和最小,那么就是最中间的两个点。这道题相当于一个位置可以有好几个点,那么就找到第n/2个点所在的那个位置即可.
考虑数位DP的套路,我们需要逐位确定.那么确定了前面的几位数字之后,我们需要求出满足前面几位数字的要求的所有数字的代价之和.由于数据范围很小,我们考虑枚举最优的终点位置,然后求出有多少种方案的最优终点位置在这里,通过分类讨论统计代价即可.预处理的时候需要预处理3个数组,f[i][j]表示各数位之和为j的i位数有多少个,s[i][j]表示各数位之和为j的i位数的数位之和(s[i][j]可以直接公式算出来,不需要DP),g[i][j]表示各数位之和为j的所有数字把数字都移到最左端/最右端的代价之和.
写的时候发现会需要枚举很多东西….复杂度略大但数据范围小可以过….
不是很好写.考试的时候感觉这道题比较裸就拿两个小时来刚,最后有一个bug(高低位弄混了)没有调出来.下午调了调A了,悲伤的故事…还是多写写数位DP吧...代码能力好弱啊...
#include<cstdio>
#include<cstring>
typedef long long ll;
int k;
ll f[70][300],s[70][300],g[70][300];//f[i][j]:i位数,数字之和为j的方案数 s[i][j]:这些数字的和,g[i][j]:i位数,全部移动到一端之外的代价之和(移动到左端或右端是一样的,每个数都有一个对称的数)
void init(int n){
f[0][0]=1;
for(int i=1;i<=n;++i){
int lim=i*(k-1);
for(int j=0;j<=lim;++j){
for(int l=0;l<k&&l<=j;++l){//if(i==2&&j==12)printf("%d %d\n",l,f[i-1][j-l]);
f[i][j]+=f[i-1][j-l];
g[i][j]+=g[i-1][j-l]+f[i-1][j-l]*l*i;
s[i][j]+=s[i-1][j-l];s[i][j]+=f[i-1][j-l]*l;
}
}
}
}
int a[100];int tot=0;
int presum[100],precost[100],sucsum[100],succost[100];
int brute(ll x){
tot=0;int sum=0;
while(x){
a[++tot]=x%k;x/=k;sum+=a[tot];
}
int i=1;
int tmp=0;
while(tmp*2<=sum){
tmp+=a[i];++i;
}
i--;
int ans=0;
for(int j=1;j<i;++j)ans+=(i-j)*a[j];
for(int j=i+1;j<=tot;++j)ans+=(j-i)*a[j];
return ans;
}
ll calc(ll n){
ll ans=brute(n);//特判掉和n相等
//printf("brute%lld\n",ans);
memset(presum,0,sizeof(presum));
memset(precost,0,sizeof(precost)); memset(a,0,sizeof(a));
memset(sucsum,0,sizeof(sucsum));memset(succost,0,sizeof(succost));
tot=0;
while(n){
a[++tot]=n%k;n/=k;
}
//a[1]:最低位 a[tot]:最高位
//下面只考虑至少有一位不一样的 ,<n的数
//终点可能在前缀部分 前缀部分的代价计算简直鬼畜...
for(int i=1;i<=tot;++i)sucsum[i]=sucsum[i-1]+a[i];//sucsum用"前缀和"的方式计算
for(int i=1;i<=tot;++i)succost[i]=succost[i-1]+sucsum[i];//succost[i]:[1,i]移动到i+1的花费
for(int i=tot;i>=1;--i){
for(int j=0;j<a[i];++j){
//考虑[i+1,tot]区间内和原数相同,第i位为j的所有数字
//presum[i+1]=[i+1,tot]区间内原数数字不带权加和
//precost[i+1]=[i+1,tot]区间内原数数字移动到i的花费
//[i,tot]此时已经确定
//分ed的位置进行讨论
//代价分成四块讨论:[i+1,tot],[i,i],[i-1,ed+1],[1,ed-1]
ll pre1=presum[i+1]+j;//确定a[i]位置为j之后[i,tot]的和
for(int ed=1;ed<i;++ed){
//枚举最后所有数字集合到的位置
//需要枚举a[ed]的值
//需要枚举一部分的和再枚举另一部分的和
for(int valed=0;valed<k;++valed){
for(int rsum=0;rsum<=(k-1)*(ed-1);++rsum){//[1,ed-1]的和 这个区间可能为空
//找出[ed+1,i-1]区间和的上下界
int lb=rsum-pre1-valed,ub=rsum-pre1+valed-1;
if(lb<0)lb=0;
if(ub>(i-ed-1)*(k-1))ub=(i-ed-1)*(k-1);
if(lb>ub)continue;
// printf("i=%d j=%d ed=%d valed=%d rsum=%d lb=%d ub=%d ans==%lld pre1==%lld\n",i,j,ed,valed,rsum,lb,ub,ans,pre1);
if(ed==i-1){
lb=ub=0;
}
for(int y=lb;y<=ub;++y){
ans+=(pre1*(i-ed)+precost[i+1])*f[i-ed-1][y]*f[ed-1][rsum];//[i,tot]
ans+=g[i-ed-1][y]*f[ed-1][rsum];//[ed+1,i-1]
ans+=f[i-ed-1][y]*g[ed-1][rsum];//[1,ed-1]
}
}
}
}
// printf("i==%d,j==%d,halfans==%lld\n",i,j,ans);
//代价分成三块讨论:[i+1,tot],[i,i],[1,i-1]
for(int ed=i;ed<=tot;++ed){//不需枚举ed的值,已经确定
int lsum=presum[ed+1],rsum=j+presum[i+1]-presum[ed],valed=(ed==i)?j:a[ed];
if(i==ed)rsum=0;
int lb=lsum-valed-rsum+1,ub=valed+lsum-rsum;//lower bound,upper bound
if(ub<0||lb>(i-1)*(k-1))continue;
//printf("i==%d j==%d ed==%d lb=%d ub=%d\n",i,j,ed,lb,ub);
if(lb<0)lb=0;
if(ub>(i-1)*(k-1))ub=(i-1)*(k-1);
//printf("i==%d j==%d ed==%d lb=%d ub=%d\n",i,j,ed,lb,ub);
ll same;
if(ed!=i)same=precost[ed+1]+(succost[ed-1]-succost[i]-sucsum[i]*(ed-i-1))+j*(ed-i);//[i,tot]移动到ed的花费
else same=precost[i+1];
for(int y=lb;y<=ub;++y){//最低i-1位的和在[lb,ub]之间都可以使得ed是一个最优终点
ans+=same*f[i-1][y];ans+=g[i-1][y];ans+=s[i-1][y]*(ed-i);
} //printf("i==%d j==%d ed==%d same==%lld ans==%lld\n",i,j,ed,same,ans);
}
//printf("i==%d,j==%d,littleans==%lld\n",i,j,ans);
}
presum[i]=presum[i+1]+a[i];precost[i]=precost[i+1]+presum[i];//从高位向低位枚举,应当用后面的元素往前更新前缀和
//printf("i==%d,ans==%lld\n",i,ans);
}
return ans;
}
int main(){
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
ll L,R;scanf("%lld%lld%d",&L,&R,&k);
/* if(R-L<=10000000){
ll sum=0;
for(ll i=L;i<=R;++i)sum+=brute(i);
printf("%lld\n",sum);
} else{*/
ll tmp=R;int cnt=0;
while(tmp){
tmp/=k;cnt++;
}
init(cnt);
printf("%lld\n",calc(R)-calc(L-1));
//}
fclose(stdin);fclose(stdout);
return 0;
}