题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3709
题意：给你一个区间，让你找平衡数的个数
题解：设dp[i][j][k]为前i位以第j位为支撑点的力矩和为k的方案数，注意的是0，00，000这些也是平衡数，所以要减掉一个len长度
1 #include<cstdio> 2 #include<cstring> 3 #define F(i,a,b) for(LL i=a;i<=b;i++) 4 typedef long long LL; 5 6 LL t,n,m,dp[20][20][2010],dig[20],len,an,an2,ii; 7 8 LL dfs(int pos,int now,int f,bool inf){ 9 if(!pos)return !f; 10 if(f<0)return 0; 11 if(!inf&&dp[pos][now][f]!=-1)return dp[pos][now][f]; 12 LL end=inf?dig[pos]:9,ans=0; 13 F(i,0,end)ans+=dfs(pos-1,now,f+(pos-now)*i,inf&&(i==end)); 14 if(!inf)dp[pos][now][f]=ans; 15 return ans; 16 } 17 18 int main(){ 19 memset(dp,-1,sizeof(dp)); 20 scanf("%lld",&t); 21 while(t--){ 22 scanf("%lld%lld",&n,&m),n--; 23 for(len=0;n;n/=10)dig[++len]=n%10; 24 for(an=0,ii=len;ii>0;ii--)an+=dfs(len,ii,0,1);an-=len; 25 for(len=0;m;m/=10)dig[++len]=m%10; 26 for(an2=0,ii=len;ii>0;ii--)an2+=dfs(len,ii,0,1); 27 printf("%lld ",an2-len-an); 28 } 29 return 0; 30 }