B-number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10837 Accepted Submission(s): 6431

Problem Description
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.

Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

Output
Print each answer in a single line.

Sample Input
13
100
200
1000

Sample Output
1
1
2
2

Author
wqb0039

Source
2010 Asia Regional Chengdu Site —— Online Contest
题目链接：hdu-3652
题解：我把叙述都写在代码里面了 注释

#include <cstring>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
const int N =1e5+100;
int dp[15][3][15];//dp[pos][str][num];
int a[15];//存数字 每一位
int gett(int str,int i)//上一位状态和这一位数字
{//作用就是更新数位状态
    if(str==0)//上一位不是1
    {
        if(i==1) return 1;//若这位为1，则return 1
        else return 0;//若这位不是1 ，则return 0
    }
    else if(str==1)//上一位为1
    {
        if(i==1) return 1;//若这位为1，则return 1
        if(i==3) return 2;//若这位为3，则return 2
        return 0;//否则，return 0
    }
    return 2;//出现过13，则 return 2
}
int dfs(int pos,int str,int num,bool limit)//pos是数位 str表示上一位是不是1 0表示不是1 1表示是1 2表示已经出现13 num是%13之后的数字 limit表示当前位的上界
{
    if(pos==-1) return num==0&&str==2;//**(重点)**题目有两个条件，num%13==0并且str==2(包含13);这样的数字才计数。
    if(!limit&&~dp[pos][str][num]) return dp[pos][str][num];//这里就是说未达到边界并且这个数已经记录过 如果记录过了那就直接加上 这就是记忆化的作用
    //这里特别提一下按位取反~和逻辑取反！的区别 如果是~就是每一位取反 针对整数类型的操作 ！是针对bool类型的操作
    int up_bound=limit?a[pos]:9,ans=0;//up_bound是上届 这个操作就是更新一下上界
    for(int i=0; i<=up_bound; i++)//这里应该是遍历下一位 可以从下面看出 它会和本位一起做一些判断 例如判断是否出现13 是否达到上界
        ans+=dfs(pos-1,gett(str,i),(num*10+i)%13,limit&&i==up_bound);//str的改变在gett函数中
        //pos-1是进行下一个数位计算 str可以标记当前数什么状态 具体上面说了 num的计算就是每一位不停%13记录余数 这里并不会影响最后结果 也就是说可以计算整个数的%13余数
        //我们从最高位开始第一次记录了当前位的上界 并且我们遍历到这个地方的时候我们就会更新一下下一位的上界 i==up_bound就是当前遍历至上界的标志
    return limit?ans:dp[pos][str][num]=ans;//如果未达到上界我们用一下dp数组记录本位的情况 如果达到了 直接返回ans 递归之下就会增加总答案数
}
int slove(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++] =x%10;//a数组逆序存储每一位
        x/=10;
    }
    return dfs(pos-1,0,0,1);//从最高位开始搜索
}
int main()
{
    int n;
    mem(dp, -1);
    while(~scanf("%d",&n)) {

        printf("%d\n", slove(n));
    }
    return 0;
}