首页 > 代码库 > hdu 4722 Good Numbers(初涉数位dp)
hdu 4722 Good Numbers(初涉数位dp)
http://acm.hdu.edu.cn/showproblem.php?pid=4722
大致题意:若一个整数的各位数字之和是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 <stdio.h> #include <iostream> #include <map> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #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\n",item,cal(y) - cal(x-1)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。