Hdu 3709 - Balanced Number

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

题目大意：
如果一个数，指定某一个数位为轴，左右两边数位和轴的距离定义为数位上数字与数位离轴所在数位的距离的乘积，如果轴左右两边数位的距离平衡，则是一个Balanced Number,求给定的$[l,r]$区间内有多少个这样的数

分析：
显然是数位DP，由于每一位都可以是数轴，所以枚举轴的位置，然后记录一个距离和，大于轴位置的数位为正值，小于轴为负值，最后检查是否和为0即可，由于需要DP数组记忆化，所以和不能是负值，所以对和加上一个初值，使区间$[-s,s]$的数映射到$[-s+d,s+d]$，需要$d>s$，由于左边最大的总距离和也就是$(10+9+\dots+2+1)*9 <500$，所以随意开一个大于500的初值作为0即可

另外做的时候一直和样例不一样，怎么也调不出来，后来想到是前导零的问题，但是加上一个bool lead参数反而容易出更多问题，没想到什么好的办法解决，后来看了题解发现，0的问题主要在于在所有的数轴位置下，0都是算作符合条件的数，所以数字长度为$len$，则0被多计算了$len-1$，最后答案减去即可

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

ll l,r;
ll dp[20][20][4000];
int a[30],pos;


ll dfs(int pos,int pivot,int pre,bool limit)
{
    if (pos==-1)
    {
        if (pre!=2000)    return 0;
        else    return 1;
    }
    if (!limit&&dp[pos][pivot][pre]!=-1)    return dp[pos][pivot][pre];
    int up = limit?a[pos]:9;
    ll ans = 0;
    for (int i = 0 ; i <= up ; i ++)
    {
        ans += dfs(pos-1,pivot,pre+(pos-pivot)*i,limit&&i==a[pos]);
    }
    if (!limit) dp[pos][pivot][pre] = ans;
    return ans;
}

ll solve(ll x)
{
    pos = 0;
    while (x)
    {
        a[pos++] = x%10;
        x /= 10;
    }
    ll ans = 0;
    for (int i = 0 ; i < pos ; i ++)
    {
        ans += dfs(pos-1,i,2000,true);
        //printf("now ans = %lld \n",ans);
    }
    return ans-pos+1;
}

int main(){

    int T;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    while (T--)
    {
        scanf("%I64d%I64d",&l,&r);
        printf("%I64d\n",solve(r)-solve(l-1));
    }
	return 0;
}