hdu 4722 Good Numbers（初涉数位dp） - c++编程基础

TOP

hdu 4722 Good Numbers（初涉数位dp）

2015-07-24 05:41:32 来源: 作者: 【大中小】浏览:6次

大致题意：若一个整数的各位数字之和是10的倍数，称这个数为good number。给出区间[A,B]，求出该区间内good number的数的个数。

第一道数位dp,折腾了半天才明白怎么回事。

设dp[site][mod]表示到第site位(由高位向低位)前面各位数字之和对10取余为mod的数的个数，进行记忆化搜索。有两个很重要的点，首先是变量up,表示是否到达边界，up为0表示没到达，up为1表示到达边界，up的取值决定后面位数上的数的取值范围，是0-9还是0-dig[site]。然后是记忆化的条件，dp[site][mod]记录的是没到达边界的情况，相当于共用的结果，这也应该的记忆化的本质，而对于到达边界的，就没必要记忆化了。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; _LL dp[25][12]; int dig[25]; _LL dfs(int site, int mod, int up) { if(site == 0) return mod == 0 ? 1 : 0; //边界。 if(!up && dp[site][mod] != -1) //注意记忆化的条件，up = 0 且 dp[site][mod] != -1 return dp[site][mod]; int len = up ? dig[site] : 9; //根据是否到达上界确定第site位的取值 _LL ans = 0; for(int i = 0; i <= len; i++) { ans += dfs(site-1, (mod+i)%10, up && (i == len) ); } if(!up) dp[site][mod] = ans; return ans; } _LL cal(_LL x) { int cnt = 0; _LL tmp = x; if(x < 0) return 0; while(tmp) { dig[++cnt] = tmp % 10; tmp /= 10; } memset(dp,-1,sizeof(dp)); return dfs(cnt,0,1); } int main() { int test; _LL x,y; scanf(%d,&test); for(int item = 1; item <= test; item++) { cin >> x >> y; memset(dp,-1,sizeof(dp)); printf(Case #%d: %I64d ,item,cal(y) - cal(x-1)); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Codeforces445B_DZY Loves Chemis..	下一篇：HDU 4770 Lights Against Dudely..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: