首页 > 代码库 > 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 }
HDU 3652 B-number 数位DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。