好贷网好贷款

HDU 4722 Good Numbers

发布时间:2016-12-5 12:34:27 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4722 Good Numbers",主要涉及到HDU 4722 Good Numbers方面的内容,对于HDU 4722 Good Numbers感兴趣的同学可以参考一下。

题意:求出给定范围内的“Good Numbers”,也就是所有数位之和可以整除10即可 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4722 思路:数位dp #include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; #define LL long long LL digit[30]; LL dp[30][30]; LL dfs(LL pos , LL pre , bool doing){ if(pos == -1) return pre == 0; if(!doing && dp[pos][pre]!=-1) return dp[pos][pre]; LL ans = 0 , npre; LL end = doing ? digit[pos] : 9; for(LL i = 0 ; i <= end ; i ++){ npre = (pre + i) % 10; ans += dfs(pos - 1, npre , doing && (i == end)); } if(!doing) dp[pos][pre] = ans; return ans; } LL calc(LL x){ LL pos = 0; memset(dp , -1,sizeof(dp)); while(x){ digit[pos ++]= x % 10; x /= 10; } return dfs(pos - 1, 0 , 1); } LL a,b,ans; int main() { int T; scanf("%d",&T); for(int ncase = 1;ncase <= T;ncase++){ scanf("%I64d %I64d",&a,&b); ans = calc(b) - calc(a - 1); printf("Case #%d: %I64d\n",ncase,ans); } return 0; }

上一篇:【热门主题:喵星人高清桌面壁纸】
下一篇:如何开启MySQL慢查询日志

相关文章

相关评论