这题其实就是不断地合并子树，跟前面例一的思想是一样的。
这个打法我觉得非常优美啊（学别人的），为什么要搞lim1和lim2呢？
是因为在区间lim1~lim2之外的都是没有用的，但是我们f[h][sum][rem]里存的是一棵完整的h层的树，所以被lim1和lim2限制的就不存进去了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; const LL N=1100; LL l,r,K; struct node{ LL a,b; bool bk; node() { bk=0;a=0;b=0; } }f[20][N][N]; LL dl[20],dr[20]; void mercy(node &x,node y){x.a+=y.a;x.b=y.b;} node dp(LL h,LL sum,LL rem,LL lim1,LL lim2) { node ans; ans.a=0;ans.b=rem; if(f[h][sum][rem].bk && !lim1 && !lim2) return f[h][sum][rem]; if(h==0) { if(sum+rem>=K) ans.a=1,ans.b=0; else ans.a=0,ans.b=sum+rem; } else { LL x=lim1 ? dl[h] : 0; LL y=lim2 ? dr[h] : 9; for(LL i=x;i<=y;i++) { mercy(ans,dp(h-1,sum+i,ans.b,(lim1&(i==x)),(lim2&(i==y)))); } } if(!lim1 && !lim2) f[h][sum][rem]=ans,f[h][sum][rem].bk=1; return ans; } int main() { freopen("a.in","r",stdin); freopen("me.out","w",stdout); scanf("%lld%lld%lld",&l,&r,&K); LL x; memset(dl,0,sizeof(dl)); memset(dr,0,sizeof(dr)); x=0;while(l) {dl[++x]=l%10;l/=10;} x=0;while(r) {dr[++x]=r%10;r/=10;} printf("%lld\n",dp(18,0,0,1,1).a); return 0; }