题目大意：定义balance数，这个数中间可以有一个中枢，左右边的力矩相等，问区间内有多少个balance数；
题目解析：定义dp[i][j][k]表示为第i位，第j位为中枢，当前和为k的个数，dfs的时候如果k已经为负数的话就可以剪枝了；
AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; typedef long long ll; ll dp[20][20][2005]; int num[20]; ll dfs(int pos,int x,ll sum,bool limit) { if(pos==-1) return sum==0; if(!limit&&dp[pos][x][sum]!=-1) return dp[pos][x][sum]; if(sum<0) return 0; int u=limit?num[pos]:9; ll ans=0; for(int i=0;i<=u;i++) { ans+=dfs(pos-1,x,sum+i*(pos-x),limit&&i==num[pos]); } if(!limit) return dp[pos][x][sum]=ans; return ans; } ll solve(ll x) { int pos=0; while(x) { num[pos++]=x; x/=10; } ll ans=0; for(int i=0;i<pos;i++) { ans+=dfs(pos-1,i,0,true); } return ans-pos+1; } int main() { ll n,m; int cas; scanf("%d",&cas); memset(dp,-1,sizeof(dp)); while(cas--) { scanf("%lld%lld",&n,&m); printf("%lld\n",solve(m)-solve(n-1)); } return 0; }