首页 > 代码库 > 【HDU 3652】 B-number (数位DP)
【HDU 3652】 B-number (数位DP)
B-number
Problem DescriptionA wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
InputProcess till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
OutputPrint each answer in a single line.
Sample Input131002001000
Sample Output1122
Authorwqb0039
Source2010 Asia Regional Chengdu Site —— Online Contest
【题意】
找出1~n范围内含有13并且能被13整除的数字的个数
【分析】
f[i][j][k]表示填i个数,模13余数为j,状态为k的方案数。
k=0表示没有‘13’且末位不为1,k=1表示没有‘13’但末位为1,k=3为含有‘13’。
这是数位DP模版题啊。。感觉我真的从难往简单做了,第一题搞的我,这酸爽!!
我还是too naive啊,一开始弄k表示状态想得超复杂,觉得要记录含不含k以及上一位是什么,其实很多状态是没用的嘛,只要知道上一位是不是1就好了,我是如此搞笑!
代码如下:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 #define LL long long10 11 int f[20][20][3],a[20];12 int c;13 14 LL ffind(int n,int k,int tt,bool flag)15 {16 if(n==0) return (tt==2&&k==0);17 if(!flag&&f[n][k][tt]!=-1) return f[n][k][tt];18 LL ans=0;19 int ed=flag?a[n]:9;20 for(int i=0;i<=ed;i++)21 {22 int nt=0;23 if(i==1) nt=1;24 if(tt==1&&i==3) nt=2;25 if(tt==2) nt=2;26 ans+=ffind(n-1,(k*10+i)%13,nt,(flag&&(i==ed)));27 }28 if(!flag) f[n][k][tt]=ans;29 return ans;30 }31 32 LL get_ans(int n)33 {34 int x=n;35 c=0;36 while(x) a[++c]=x%10,x/=10;37 return ffind(c,0,0,1);38 }39 40 int main()41 {42 memset(f,-1,sizeof(f));43 int n;44 while(scanf("%d",&n)!=EOF)45 {46 LL ans=get_ans(n);47 printf("%lld\n",ans);48 }49 return 0;50 }
记得100年前,没做过几道数位DP的我比赛时打了个高精数位DP那么勇猛,还AC了,现在真是返老还童了ORZ!!
2016-10-08 21:28:51
【HDU 3652】 B-number (数位DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。