首页 > 代码库 > HDU 3652 B-number 数位DP

HDU 3652 B-number 数位DP

题目大意:给出一个数n,求1~n中满足:即含有13(连续),有能被13整除的数的个数.

题目思路:数位DP,一开始读错题意了,以为13可以不连续……,比较水的数位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 int num[20],dp[25][25][25];17 18 //st==0 前一位不为119 //st==1 前一位为120 //st==2 已含1321 22 long long dfs(int pos,int st,int limit,long long k)23 {24     if(pos<0)25         return st==2&&k==0;26 27     if(!limit && dp[pos][st][k]!=-1)28         return dp[pos][st][k];29     int len=limit?num[pos]:9;30     long long ans=0;31     for(int i=0;i<=len;i++)32     {33         long long temp=(k*10+i)%13;34         if(st==0 && i==1)35             ans+=dfs(pos-1,1,limit&&i==len,temp);36         else if(st==0 && i!=1)37             ans+=dfs(pos-1,0,limit&&i==len,temp);38         else if(st==1 && i==3)39             ans+=dfs(pos-1,2,limit&&i==len,temp);40         else if(st==1 && i==1)41             ans+=dfs(pos-1,1,limit&&i==len,temp);42         else if(st==1)43             ans+=dfs(pos-1,0,limit&&i==len,temp);44         else45             ans+=dfs(pos-1,2,limit&&i==len,temp);46     }47     if(!limit)48         dp[pos][st][k]=ans;49     return ans;50 }51 52 long long solve(long long a)53 {54     memset(dp,-1,sizeof(dp));55     int len=0;56     while(a)57     {58         num[len++]=a%10;59         a/=10;60     }61     long long ans=dfs(len-1,0,1,0);62     return ans;63 }64 65 int main()66 {67     long long n;68     while(scanf("%lld",&n)!=EOF)69     {70         long long ans=solve(n);71         printf("%lld\n",ans);72     }73     return 0;74 }
View Code

 

HDU 3652 B-number 数位DP