首页 > 代码库 > 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 }
View Code

 

HDU 3555 Bomb 数位DP