bzoj3598: [Scoi2014]方伯伯的商场之旅

传送门

大佬的题解：哇我省选秒A了这道题，不过就是一道水题嘛

我：？？？

奥妙重重的数位dp，虽然其实似乎比数数好一点。

先考虑把所有石头都移到第1堆，记忆化搜索算出总贡献。

然后把石头往后移，记忆化搜索n次，第i次搜索算出把那些从i移动到i+1可以减少代价的石头堆移到i+1减少的代价。

//Achen
#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<queue> #include<cmath>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--) typedef long long LL; typedef double db; using namespace std; LL L,R,K,f[401][4007],lim[41]; template<typename T>void read(T &x) { char ch=getchar(); x=0; T f=1; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; } LL dfs1(int pos,int now,int L) { if(!pos) return now; if(!L&&f[pos][now]!=-1) return f[pos][now]; LL rs=0,up=L?lim[pos]:K-1; For(i,0,up) rs+=dfs1(pos-1,now+i*(pos-1),(L&(i==up))); if(!L) f[pos][now]=rs; return rs; } LL dfs2(int pos,int aim,int now,int L) { if(now<0) return 0; if(!pos) return now; if(!L&&f[pos][now]!=-1) return f[pos][now]; LL rs=0,up=L?lim[pos]:K-1; For(i,0,up) rs+=dfs2(pos-1,aim,now+(pos>=aim?i:-i),(L&(i==up))); if(!L) f[pos][now]=rs; return rs; } LL solve(LL n) { LL tp=n; lim[0]=0; while(tp) { lim[++lim[0]]=tp%K; tp/=K; } memset(f,-1,sizeof(f)); LL rs=dfs1(lim[0],0,1); For(i,2,lim[0]) { memset(f,-1,sizeof(f)); rs-=dfs2(lim[0],i,0,1); } return rs; } int main() { #ifdef DEBUG freopen(".in","r",stdin); freopen(".out","w",stdout); #endif read(L); read(R); read(K); printf("%lld\n",solve(R)-solve(L-1)); return 0; }