HDU 3709 Balanced Number(数位dp)

题目链接：[kuangbin带你飞]专题十五 数位DP F - Balanced Number

题意

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

思路

遍历每一位做为平衡点，进行搜索，sum保存数字乘以距离的和，若sum为0，则说明平衡。
要注意因为遍历了len次，所以0多加了len－1次。
还有个小技巧是当sum<0时就可以直接return了，可以加速。因为，len由大到小的过程中，sum是由大到小的变化，但绝不会小于0，否则就是不能平衡。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define LL long long
LL dp[20][20][2000];
int dis[20];

LL dfs(int len, int pos, int sum, bool flag)
{
    if(len < 0)
        return sum?0:1;
    if(sum < 0)
        return 0;
    if(!flag && dp[len][pos][sum] != -1)
        return dp[len][pos][sum];
    LL ans = 0;
    int end = flag?dis[len]:9;
    for(int i=0; i<=end; i++)
    {
        ans += dfs(len-1, pos, sum+(len-pos)*i, flag&&i==end);
    }

    if(!flag)
        dp[len][pos][sum] = ans;
    return ans;
}

LL solve(LL n)
{
    int len = 0;
    while(n)
    {
        dis[len++] = n%10;
        n /= 10;
    }
    LL ans = 0;
    for(int i=0; i<len; i++)
        ans += dfs(len-1, i, 0, 1);
    return ans - (len-1);
}

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