G - B-number

 HDU - 3652 
A 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 Input 13 100 200 1000 Sample Output 1 1 2 2 Hint

含有数字13和能够被13整除的数的个数

#include using namespace std; int dp[12][15][2][10];///dp[i][j][k][z]：i:处理的数位，j:该数对13取模以后的值，k:是否已经包含13,z结尾的数,判断13所用 int bit[12]; int dfs(int pos,int num,bool t,int pre,bool flag) { if(pos==-1)return t&&(num==0); if(!flag && dp[pos][num][t][pre]!=-1) return dp[pos][num][t][pre]; int end=flag?bit[pos]:9; int ans=0; for(int i=0;i<=end;i++) ans+=dfs(pos-1,(num*10+i)%13,t||(pre==1&&i==3),i,flag&&(i==end)); if(!flag)dp[pos][num][t][pre]=ans; return ans; } int calc(int n) { int pos=0; while(n) { bit[pos++]=n%10; n/=10; } return dfs(pos-1,0,0,0,1); } int main() { int n; memset(dp,-1,sizeof(dp)); while(scanf("%d",&n)==1) printf("%d ",calc(n)); return 0; }