首页 > 代码库 > hdu 3555 Bomb(数位dp)
hdu 3555 Bomb(数位dp)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3555
题目大意:就是给你一个数n,判断从0到n有多少个数含有数字49.。。。。。
是不是觉得跟hdu2089很相似呀。。。
思路:跟hdu2089一样的,注意给出的数比较大,所以这儿用__int64 。。。。
code:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; __int64 dp[25][3]; void Init() { memset(dp,0,sizeof(dp)); int i; dp[0][0]=1; for(i=1;i<=20;i++) { dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; } } __int64 solve(__int64 n) { __int64 i,len=0,ans,flag,digit[25]; memset(digit,0,sizeof(digit)); while(n) { digit[++len]=n%10; n/=10; } ans=0; flag=0; for(i=len;i>0;i--) { //printf("%d ",ans); ans+=dp[i-1][2]*digit[i]; if(flag) { ans+=dp[i-1][0]*digit[i]; } if(!flag&&digit[i]>4) { ans+=dp[i-1][1]; } if(digit[i+1]==4&&digit[i]==9) { flag=1; } } return ans; } int main() { Init(); int T; __int64 n; scanf("%d",&T); while(T--) { scanf("%I64d",&n); printf("%I64d\n",solve(n+1)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。