HDU-3709 Balanced Number (数位DP)

思路：这题的难点在于判断是否该数是平衡数，解决方法是枚举力矩o的位置，计算每一位n累加的(n-o)*i的值是否等于0。

Code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int a[20];
 5 __int64 dp[20][20][2005];//中心在i, j位值为k时的数量
 6 
 7 __int64 dfs(int cur, int o, int num, bool limit) {
 8     if (!limit && ~dp[o][cur][num]) return dp[o][cur][num];
 9     if (cur == 0) return num == 0;
10     int up = limit ? a[cur] : 9;
11     __int64 ans = 0;
12     for (int i = 0; i <= up; ++i)
13         ans += dfs(cur-1, o, (cur-o)*i+num, limit && i == a[cur]);
14     if (!limit) dp[o][cur][num] = ans;
15     return ans;
16 }
17 
18 __int64 cal(__int64 x) {
19     int len = 0;
20     while(x) {
21         a[++len] = x % 10;
22         x /= 10;
23     }
24     __int64 ans = 0;
25     for (int i = 1; i <= len; ++i)
26         ans += dfs(len, i, 0, 1);
27     return ans-len+1;
28 }
29 
30 int main() {
31     int T;
32     __int64 x, y;
33     cin>>T;
34     memset(dp, -1, sizeof(dp));
35     while(T--) {
36         cin>>x>>y;
37         cout<<cal(y)-cal(x-1)<<endl;
38     }
39 
40     return 0;
41 }