Balanced Number

题解：dp[ i ][ j ][ k ]表示第i个位置，支点是j，支点左右两边的重量之差是k。当k==0时，说明这个数是Balanced Number。充分利用了回溯这个过程！

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 ll a,b,n;
 9 ll num[20],dp[20][20][4000];
10 
11 ll DFS(int pos,int res,int sum,bool F){
12     if(sum<0) return 0;         
13     if(pos==-1) return sum==0;
14     if(!F&&dp[pos][res][sum]!=-1) return dp[pos][res][sum];
15     
16     int maxv=F?num[pos]:9;
17     ll ans=0;
18     for(int i=0;i<=maxv;i++) ans=ans+DFS(pos-1,res,sum+i*(pos-res),F&&i==maxv);
19     
20     if(!F) dp[pos][res][sum]=ans;
21     return ans;
22 }
23 
24 ll Solve(ll temp){
25     if(temp==0) return 1;
26     int cnt=0;
27     while(temp){
28         num[cnt++]=temp%10;
29         temp/=10;
30     }
31     ll ans=0;
32     for(int i=cnt-1;i>=0;i--) ans=ans+DFS(cnt-1,i,0,true);         //枚举支点，非常机智，放在深搜的外面
33     return ans-cnt+1;          //因为0，00，。。。，000000，。。。都是符合的，所以要减去重复的。
34 }
35 
36 int main()
37 {   memset(dp,-1,sizeof(dp));
38     cin>>n;
39     while(n--){ cin>>a>>b; cout<<Solve(b)-Solve(a-1)<<endl; }
40     return 0;
41 }