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

题意：给定区间[a,b]，求区间内平衡数的个数。所谓平衡数即有一位做平衡点，左右两边数字的力矩相等。

求力矩很显然可以想到dp[len][mid][cau]，mid表示对称点，cau表示力矩大小。

然后很显然的记忆化索索

#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef long long ll;ll x , y , dp[20][20][2000];int dig[20];ll dfs(int len , int mid , int cau , int flag) {    if(!len)        return cau == 0;    if(cau < 0)        return 0;    if(!flag && dp[len][mid][cau] != -1)        return dp[len][mid][cau];    int t = flag ? dig[len] : 9;    ll sum = 0;    for(int i = 0 ; i <= t ; i++) {        sum += dfs(len - 1 , mid , cau + i * (len - mid) , flag && i == t);    }    if(!flag)        dp[len][mid][cau] = sum;    return sum;}ll Gets(ll gg) {    memset(dp , -1 , sizeof(dp));    int len = 0;    if(gg < 0)        return 0;    if(gg == 0)        return 1;    while(gg) {        dig[++len] = gg % 10;        gg /= 10;    }    ll ans = 0;    for(int i = len ; i >= 1 ; i--) {        ans += dfs(len , i , 0 , 1);    }    return ans - (len - 1);}int main() {    int t;    scanf("%d" , &t);    while(t--) {        scanf("%lld%lld" , &x , &y);        printf("%lld\n" , Gets(y) - Gets(x - 1));    }    return 0;}

hdu 3709 Balanced Number（数位dp）