hdu 4722（动态规划-数位dp）

川长思鸟来 2022-05-31 12:25 224阅读 0赞

问题描述:

If we sum up every digit of a number and the result can be exactly divided by 10, we say this number is a good number.   
You are required to count the number of good numbers in the range from A to B, inclusive.

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.   
Each test case comes with a single line with two numbers A and B (0 <= A <= B <= 1018).

Output

For test case X, output "Case \#X: " first, then output the number of good numbers in a single line.

Sample Input

2
    1 10
    1 20

Sample Output

Case #1: 0
    Case #2: 1

题目题意:问区间\[l,r\]内有多少数满足数位之和能被10整除

题目分析:数位dp，dp\[len\]\[sum\]，len表示位数长度，sum表示前面位数的和

分享一个博主的数位dp总结[点击打开链接][Link 1]

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #define ll long long
    using namespace std;
    
    ll dp[25][2000];
    int num[25];
    
    ll dfs(int len,ll sum,bool limit)
    {
        if (len<1) return (ll) sum%10==0;
        if (!limit&&dp[len][sum]) return dp[len][sum];
        int Max=limit?num[len]:9;
        ll ans=0;
        for (int i=0;i<=Max;i++) {
            ans+=dfs(len-1,sum+i,limit&&num[len]==i) ;
        }
        if (!limit) dp[len][sum]=ans;
        return ans;
    }
    ll solve(ll n)
    {
        int len=0;
        if (n<0) return 0;
        while (n) {
            num[++len]=n%10;
            n=n/10;
        }
        return dfs(len,0,true);
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        memset (dp,0,sizeof (dp));
        for (int i=1;i<=t;i++) {
            ll left,right;
            scanf("%lld%lld",&left,&right);
            printf("Case #%d: %lld\n",i,solve(right)-solve(left-1));
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/wust_zzwh/article/details/52100392