HDU 3709 Balanced Number （数位DP）

题意：

　　找出区间内平衡数的个数，所谓的平衡数，就是以这个数字的某一位为支点，另外两边的数字大小乘以力矩之和相等，即为平衡数。

思路：

　　一开始以为需要枚举位数，枚举前缀和，枚举后缀和，一旦枚举起来就会MLE。

　　其实只需要3维 [第几位][和][轴位置]，对于轴的位置是需要枚举的，每个位都是有可能的，比如900和7都是一个平衡数。注意这道题的区间下限可能为0，而0也是平衡数，这在拆十进制的时候len=0的，最好将0特处理。

 #include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x7f3f3f3f

 #define LL long long

 #define ULL unsigned long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 LL f[N][][N], bit[N];

 //[第几位][和][轴]

 LL dfs(int i,int sum,int mid,bool e)

 {

     if(i==)    return sum==;

     if(sum< || sum>=)    return ;

     if(!e && ~f[i][sum][mid])    return f[i][sum][mid];

     LL ans=;

     int u= e? bit[i]: ;

     for(int d=; d<=u; d++)

     {

         if(sum== && i==mid && d==)    continue;    //首位是mid，必须不为0

         ans+=dfs(i-, sum+(i-mid)*d, mid, e&&d==u);    //注意不能为负

     }

     return e? ans: f[i][sum][mid]=ans;

 }

 LL cal(LL n)

 {

     if(n<)        return ;

     int len=;

     while(n)    //拆数

     {

         bit[++len]=n%;

         n/=;

     }

     LL ans=;    //dfs是没有统计0的，因为len=0是不会执行dfs的

     for(int i=; i<=len; i++)

         ans+=dfs(len, , i, true);

     return ans;

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     memset(f,-,sizeof(f));

     LL L,R;int t;cin>>t;

     while( t-- )

     {

         cin>>L>>R;

         cout<<cal(R)-cal(L-)<<endl;

     }

     return ;

 }

AC代码