hdu 3709 Balanced Number (数位dp)
题目链接 题意：找到某区间中平衡数的个数。所谓平衡数是指，存在某个位置，值得两边的力矩相等。举个例子。。比如14326，如果把4作为中间。。那么左边=11=1 右边=31+22+62=19。。。 思路：枚举中间的pivot。。。注意如果是个位数也是平衡数（就是认为两边的力矩都是0了。。。），所以每一个位置都可能是平衡位置。。枚举的时候从1到len… 一开始我是分别记录两边的值。。非常浪费空间。。。然而发现其实没必要。。我们只关心左边是否相等。。而不关心左右的值到底是多少。。所以可以把两边的值带符号合并成一个值（pivot左边为+，pivot右边为负）。。。如果最后为0。。说明左右相等。。。
以及。。这个值(设为sum)是递减的。。。所以任何时刻如果sum<0。。那么狗带。。算一个剪枝。。而且避免了下标为负。。。
以及，关于前导0的问题。。。有些题目不允许前导0.。。。但是并不是所有不允许前导0的都需要特别处理。。。像这道。。前导0不会导致更新答案。。。所以不用管。。。 但是要注意。。。由于0，00,000,0000都是合法的balanced数。。。然而其实他们是一个数。。多加了len-1次。。记得减去。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月17日 星期四 17时08分59秒
4File Name :code/hdu/3709.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33LL l,r;
34int T;
35int digit[30];
36LL dp[20][2000][20]; //窝要判断左边和右边是否相等，并不需要分别统计两边，只要把数值带上符号，统计左右两边的和即可。
37 //如果相等，那么和为0.这样能节省很多空间。
38LL dfs( int pos,int sum ,int pivot,bool limit)
39{ //不用考虑前导0，因为前导0的存在并不会对答案有任何贡献.
40 if (pos==0) return sum==0;
41 if (sum<0) return 0; //由于sum是递减的。。所以sum一旦小于0绝对药丸。。。肯定对答案没贡献。
42 //也算作一个剪枝..
43 if (!limit&&dp[pos][sum][pivot]!=-1) return dp[pos][sum][pivot];
44
45 int mx = limit?digit[pos]:9;
46 LL res = 0LL ;
47 for ( int i = 0 ; i <= mx ; i++)
48 {
49 res+=dfs(pos-1,sum+(pos-pivot)*i,pivot,limit&&i==mx);
50 }
51
52 // cout<<"res:"<<res<<endl;
53 return limit?res:dp[pos][sum][pivot]=res;
54}
55LL solve (LL n)
56{
57 // if (n<0) return 0;
58 LL len = 0;
59 ms ( digit , 0 );
60 while (n)
61 {
62 digit[++len] = n % 10;
63 n /= 10;
64 }
65
66 LL res = 0LL ;
67 for ( int piv = 1 ; piv <= len ; piv++) //pivot要从1开始枚举到len。因为个位数也是满足条件的数（两边都为0，相等）
68 {
69 res += dfs (len,0,piv,true);
70// cout<<"res:"<<res<<endl;
71 }
72
73 return res-(len-1); //0,00,000,0000都是满足条件的，然而其实他们是一个数，多算了len-1次。
74}
75int main()
76{
77 #ifndef ONLINE_JUDGE
78 freopen("code/in.txt","r",stdin);
79 #endif
80
81 ios::sync_with_stdio(false);
82 int T;
83 cin>>T;
84 ms(dp,-1);
85 while (T--)
86 {
87 cin>>l>>r;
88 LL ans = solve (r) - solve (l-1);
89 // cout<<"-1:"<<solve(-1)<<endl;
90 cout<<ans<<endl;
91 }
92
93 #ifndef ONLINE_JUDGE
94 fclose(stdin);
95 #endif
96 return 0;
97}