首页 > 代码库 > HDU 3555 Bomb 数位DP
HDU 3555 Bomb 数位DP
题目大意:求1~n中含有‘49’的数字的个数。
题目思路:数位DP水题,看代码吧
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #include<stdio.h> 6 #include<stdlib.h> 7 #include<queue> 8 #include<math.h> 9 #include<map>10 #define INF 0x3f3f3f3f11 #define MAX 100000512 #define Temp 100000000013 14 using namespace std;15 16 //st==0 不含417 //st==1 含418 //st==2 含4919 20 int num[MAX];21 long long dp[50][50];22 23 long long dfs(int pos,int st,int limit)24 {25 if(pos<0)26 return st==2;27 if(!limit && dp[pos][st]!=-1)28 return dp[pos][st];29 long long ans=0;30 int len=limit?num[pos]:9;31 for(int i=0;i<=len;i++)32 {33 if(st==0)34 {35 if(i==4)36 ans+=dfs(pos-1,1,limit&&i==len);37 else38 ans+=dfs(pos-1,0,limit&&i==len);39 }40 else if(st==1)41 {42 if(i==9)43 ans+=dfs(pos-1,2,limit&&i==len);44 else if(i==4)45 ans+=dfs(pos-1,1,limit&&i==len);46 else47 ans+=dfs(pos-1,0,limit&&i==len);48 }49 else if(st==2)50 {51 ans+=dfs(pos-1,2,limit&&i==len);52 }53 }54 if(!limit)55 dp[pos][st]=ans;56 return ans;57 }58 59 long long solve(long long a)60 {61 memset(dp,-1,sizeof(dp));62 int len=0;63 while(a)64 {65 num[len++]=a%10;66 a/=10;67 }68 long long ans=dfs(len-1,0,1);69 return ans;70 }71 72 int main()73 {74 int T;75 long long n;76 scanf("%d",&T);77 while(T--)78 {79 scanf("%lld",&n);80 long long ans=solve(n);81 printf("%lld\n",ans);82 }83 return 0;84 }
HDU 3555 Bomb 数位DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。