BZOJ3598[Scoi2014]方伯伯的商场之旅 数位DP

看到数据范围很容易想到数位 DP 然后就很容易想到枚举每一位作为最优点
我们可以发现对于一个数字 如果他的最优点确定了 那离最优点越远 花费越高
我们可以先将所有的数字全合并到第一个点(用数位DP求) 然后依次枚举从 i -> i+1 更优的数字有多少个 在这里 我们只需要求出他对答案的贡献即可 从 i -> i+1 前 i 位都要多走一次（加上） 后面都要少走一次（减去） 我们在数位DP时记录这个差值 如果当某一时刻数位 DP 中的 sum<0 那么往后一定只会更小 那对答案就没有贡献 直接 return0 即可
这样暴力转移每一位向后一位的贡献就可以啦~

具体的看代码就很容易懂qaq

#include<bits/stdc++.h>
#define ll long long
#define cl(x) memset(x,0,sizeof x)
using namespace std;
inline ll read(){
    ll x=0;scanf("%lld",&x);return x; 
}
ll l,r,k,top,f[55][5555],q[55];
ll dfs1(int pos,ll sum,bool flag){
    if(!pos) return sum;
    if(!flag&&f[pos][sum]) return f[pos][sum];
    ll ans=0,mx=flag?q[pos]:k-1;
    for(int i=0;i<=mx;i++) ans+=dfs1(pos-1,sum+(pos-1)*i,flag&&i==mx); 
    if(!flag) f[pos][sum]=ans;
    return ans;
}
ll dfs2(int pos,ll sum,int sit,bool flag){
    if(sum<0) return 0;
    if(!pos) return sum;
    if(!flag&&f[pos][sum]) return f[pos][sum];
    ll ans=0,mx=flag?q[pos]:k-1;
    for(int i=0;i<=mx;i++){
        if(pos>=sit) ans+=dfs2(pos-1,sum+i,sit,flag&&i==mx);
        else if(pos<sit) ans+=dfs2(pos-1,sum-i,sit,flag&&i==mx);
    } 
    if(!flag) f[pos][sum]=ans;
    return ans;
}
ll calc(ll x){
    top=0;
    ll ans=0;
    while(x) q[++top]=x%k,x/=k;
    cl(f),ans+=dfs1(top,0,1);
    for(int i=2;i<=top;i++) cl(f),ans-=dfs2(top,0,i,1);
    return ans;
}
int main(){
    l=read(),r=read(),k=read();
    cout<<calc(r)-calc(l-1)<<endl;
}