题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3598
TJ：https://www.cnblogs.com/Zinn/p/9351218.html
核心：先确定一个中心，再考虑变动中心带来的好处。
用dfs实现很清楚。把填到这一位为止带来的代价写进参数里。但dfs的值表示的是把后面的位都填好带来的代价，所以要开long long。
这么一想好像也没啥？？？
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=60,S=1205; int K,dg[N]; ll l,r,dp[N][S]; ll dfs(int p,int s,bool fx) { if(!p)return s; if(!fx&&dp[p][s]!=-1)return dp[p][s]; int lm=K-1;if(fx)lm=dg[p]; ll ret=0; for(int i=0;i<=lm;i++) ret+=dfs(p-1,s+i*(p-1),fx&(i==dg[p])); if(!fx)dp[p][s]=ret; return ret; } ll dfs(int p,int s,int zx,bool fx) { if(!p)return s>0?s:0; if(!fx&&dp[p][s]!=-1)return dp[p][s]; int lm=K-1;if(fx)lm=dg[p]; ll ret=0; for(int i=0;i<=lm;i++) ret+=dfs(p-1,p>zx?s+i:s-i,zx,fx&(i==dg[p])); if(!fx)dp[p][s]=ret; return ret; } ll calc(ll x) { int n=0; while(x)dg[++n]=x%K,x/=K; memset(dp,-1,sizeof dp);// ll ret=dfs(n,0,1); for(int i=1;i<n;i++) { memset(dp,-1,sizeof dp); ret-=dfs(n,0,i,1); } return ret; } int main() { scanf("%lld%lld%d",&l,&r,&K); printf("%lld\n",calc(r)-calc(l-1)); return 0; }
bzoj 3598 [Scoi2014]方伯伯的商场之旅——数位dp
原文：https://www.cnblogs.com/Narh/p/9400285.html