首页 > ACM题库 > HDU-杭电 > HDU 4722-Good Numbers-动态规划-[解题报告]HOJ
2015
09-17

HDU 4722-Good Numbers-动态规划-[解题报告]HOJ

Good Numbers

问题描述 :

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.

输入:

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).

输出:

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).

样例输入:

2
1 10
1 20

样例输出:

Case #1: 0
Case #2: 1
Hint
The answer maybe very large, we recommend you to use long long instead of int.

网络赛被一道数位DP给难住了,暑假自己搞DP也有一段时间了,有点不甘心啊!  而且赛后各个主要的博客数位DP的解题报告也纷纷冒出来了,我也来凑凑热闹,写一道DP,这道数位DP是从电子幼体的博文中找的,看了半天,慢慢理解了,经过多次修改终于A了,拖到今天才开始整理,感觉自己能差不多掌握这道题了!

题目地址:hdu 4722

题目大意是:一个数被称为good number是指各个位上的数之和能被10整除;  求[A,B]范围内的数有多少个满足要求! (0 <= A <= B <= 1018).

用数位DP的话,顶多18位,采用DFS+记忆化搜索+枚举的方法实现数位DP,可能也有其他方法,但是这里先整理这一种方法!

枚举的思想主要借助DFS来实现,对于每一位,都有大概0-9十种可能,除了最高位与所要比较的数的最高位一样,那么次高位也得根据最高位是否相同,来看这位是有几种情况,对于当前位取的这种情况,继续递归下去,看下一位有多少种情况,则把当前位各个情况加起来就是当前位取0-9的所有情况的总和,当然得先看当前位是否能取的0-9这十种情况;  所以DP状态dp[i][j]表示从高位开始取……

比如说,求小于B 的数中满足要求的所有数,假设没有说是整除10的话,那么咱只要判断每一位有多少种可能相乘就好了,但是需要整除10的话就需要记录判断到某位时,前面的高位到达这一位时对10取模的结果,需要记录两种状态,判断到某一位还有这位模10的结果,但是到达某一位时有时候这一位可以取0–9,有的不能,所以只记录能的,不能的在递归……    递归过程中加上一个标志变量,标志着这一位可以取0–9啊,还是0–dig[i] 到这一位的最大值,如果递归时没用到最大值,那么下一位可以用0–9,而且该状态可以持续下去

当然注意这道题目的数据范围,需要用long long

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
#define LL  __int64
const int MAXN = 111;


LL dp[MAXN][11]={0};///注意这里的范围,注意这里的dp[i][j],i表示位,表示最低位是第i位,
///然后该位上可以放0-9这十种情况下的数目
int dig[MAXN]={0};
LL dfs(int p,int m,bool flag)
{
    if(p==0)return (m==0);
    if(flag&&dp[p][m]!=-1)return dp[p][m];
    int len=flag?9:dig[p];

    LL res=0;
    for(int i=0;i<=len;++i)
    {
        res+=dfs(p-1,(m+i)%10,flag||i!=len);
    }
    if(flag) dp[p][m]=res;
    return res;
}


LL get(LL x)
{
    if(x<0)return 0;
    //memset(dig,0,sizeof(dig));

    int tot=0;
    while(x!=0)
    {
        dig[++tot]=x%10;
        x/=10;
    }
    return dfs(tot,0,0);
}

int main()
{
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    int cas=1;
    while(t--)
    {
        LL x,y;
        cin>>x>>y;
         printf("Case #%d: %I64d\n",cas++,get(y)-get(x-1));
       // cout<<"Case #"<<cas++<<": "<<get(y)-get(x-1)<<endl;
        // printf("Case #%d: %I64d\n",cas++,get(y)-get(x-1));
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zhangyanxing666/article/details/11888349