hdu 3709 Balanced Number(平衡数）--数位dp

佚名 6年前 (2019-04-22) 随笔 1959人围观抢沙发百度已收录

Balanced Number

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 9036 Accepted Submission(s): 4294

Problem Description A balanced number is a non-negative integer that can be balanced if a pivot is placed at some digit. More specifically, imagine each digit as a box with weight indicated by the digit. When a pivot is placed at some digit of the number, the distance from a digit to the pivot is the offset between it and the pivot. Then the torques of left part and right part can be calculated. It is balanced if they are the same. A balanced number must be balanced with the pivot at some of its digits. For example, 4139 is a balanced number with pivot fixed at 3. The torqueses are 4*2 + 1*1 = 9 and 9*1 = 9, for left part and right part, respectively. It's your job
to calculate the number of balanced numbers in a given range [x, y].

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 Input The input contains multiple test cases. The first line is the total number of cases T (0 < T ≤ 30). For each case, there are two integers separated by a space in a line, x and y. (0 ≤ x ≤ y ≤ 10 ¹⁸).

Output For each case, print the number of balanced numbers in the range [x, y] in a line.

Sample Input 2 0 9 7604 24324

Sample Output 10 897 分析：对于这道题，如果一个数中每个数位到支点的距离*这个数位的和为0，那么这个数为平衡数.这样我们定义状态就要考虑力矩和和支点.支点可以在dfs前枚举得到，力矩和可以在处理每个数位的时候得到.但是这个算法是有缺陷的，例如0000,000000也会被统计，我们只需要减去给定范围0全是0的数的个数即可.这里可以进行一个小小的优化，如果力矩和已经为负数，说明已经处理到了支点左边，接着处理下去绝对会小于0,那么回溯即可

#include<iostream>
#include<string.h>
#define ll long long
using namespace std;
ll shu[20], dp[20][20][2000];//dp[i][j][k],i是长度，j是支点，k是力矩和,dp[i][j][k]是以j为支点的平衡数的数量
ll dfs(ll len, ll zhidian, ll sum, bool shangxian)
{
    if (len == 0)
        return sum == 0 ? 1 : 0;
    if (sum < 0)//因为力矩和是从支点右边开始算的（sum>0）,如果左边的力矩都处理完之后sum<0,那一定不是平衡数
        return 0;
    if (!shangxian&&dp[len][zhidian][sum]!=-1)
        return dp[len][zhidian][sum];
    ll mx, cnt = 0;
    mx = (shangxian ? shu[len] : 9);
    for (ll i = 0; i <= mx; i++)//注意是<=
    {
        ll temp = sum;
        temp = temp + (len - zhidian)*i;//len会不断的被return ,细细体会
        cnt = cnt + dfs(len - 1, zhidian, temp, i == mx && shangxian);
    }
    if (!shangxian)
        dp[len][zhidian][sum] = cnt;
    return cnt;
}

ll solve(ll n)
{
    ll len = 0;
    while (n)
    {
        shu[++len] = n % 10;
        n = n / 10;
    }
    ll ans = 0;
    for (ll i = 1; i <= len; i++)//支点是从1开始，因为最高位的数一定不是平衡数
        ans = ans + dfs(len, i, 0, true);
    return ans - (len - 1);//如果0是支点，程序也会判断是平衡数，但是不符合题意
}
int main()
{
    ll l, r, t;
    scanf("%lld", &t);
    memset(dp,-1,sizeof(dp));//如果默认0会TLE
    while (t--)
    {
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", solve(r) - solve(l - 1));
    }
    return 0;
}