hdu3709+数位dp

给定一个计算公式，如果数位的前一部分的和等于后一部分，那么就是平衡数，问有多少个这样的数？？

枚举中心，在dfs就行了 注意重复的就行了

#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int Maxn=20;
int a[Maxn];
ll l,r,dp[Maxn][1500][20];
ll (int pos,int sum,int center,bool limit)
{
    if(pos==0)  return  sum==0;
    if(sum<0)   return 0;
    if(!limit && dp[pos][sum][center]!=-1) return dp[pos][sum][center];
    int up=limit?a[pos]:9;
    ll res=0;
    for(int i=0;i<=up;i++)
		res+=dfs(pos-1,sum+i*(pos-center),center,limit&&i==up);
    if(!limit) dp[pos][sum][center]=res;
    return res;
}
ll solve(ll x)
{
	int pos=0;
    while(x){  a[++pos]=x%10;x/=10;  }
    ll res=0;
    for(int i=pos;i>=1;i--)
    	res+=dfs(pos,0,i,1);
    return res-pos+1; 
}
int main()
{
	int T;
	scanf("%d",&T);
	memset(dp,-1,sizeof(dp));
	while(T--)
	{
		scanf("%I64d%I64d",&l,&r);
		printf("%I64dn",solve(r)-solve(l-1));
	}
    return 0;
}