hdu3709 Balanced Number 数位DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3709

题目大意就是求给定区间内的平衡数的个数

要明白一点：对于一个给定的数，假设其位数为n，那么可以有n个不同的位作为支点，但每次只能有一个支点

定义dp[len][pos][k]，len表示当前还需处理的位数，pos表示当前的所选的支点的位置，k表示计算到当前的力矩之和（即从最高位到第len+1位）

容易知道如果在某一个len>1的位置k已经小于0，那么就可以直接剪枝

代码如下：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 int bit[20];
 7 long long int dp[20][20][2000];
 8 long long  int x,y;
 9 
10 
11 long long int dfs(int len,int pos,int sum,bool flag )
12 {
13     long long int ans=0;
14    if(len==0 ) return sum==0;
15    if(sum<0) return 0;
16    if(flag && dp[len][pos][sum]>=0) return dp[len][pos][sum];
17 
18    int tmp=flag?9:bit[len];
19 
20    for(int i=0;i<=tmp;i++)
21    {
22        int n_sum=sum;
23        n_sum+=i*(len-pos);
24        ans+=dfs(len-1,pos,n_sum,flag||i<tmp);
25    }
26    if(flag) dp[len][pos][sum]=ans;
27    return ans;
28 }
29 long long int solve(long long int n)
30 {
31    int len=0;
32    while(n) bit[++len]=n%10,n/=10;
33    long long int ans=0;
34    for(int i=1;i<=len;i++)
35    {
36       ans+=dfs(len,i,0,0);
37    }
38 
39   return ans-(len-1);
40    
41 }
42 int main()
43 {
44    int t;
45    scanf("%d",&t);
46    while(t--)
47    {
48        scanf("%64d %64d",&x,&y);
49        memset(dp,-1,sizeof(dp));
50        cout<<solve(y)<<endl;
51     
52    }
53    return 0;
54 }