G - B-number
第一个数位dp题目。。。
题意：给你一个数n，要你求出从1到n中有多少个数满足能被13整除且含有子串“13”
思路：看求区间内某个条件的数的个数，所以首先想到数位dp，运用数位dp，开个三位数组 ，记录余数，状态等
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
int a[20];
int dp[20][20][3];//dp[i][j][k]; i表示位数，j表示余数，k是三种操作状况，0：末尾不是1，1：末尾是1,2：前面数字中含有"13"
int dfs(int pos,int mod,int pre,int limit){ //limit记录上限
int mod1,pre1;
if(pos<=0)
return mod==0&&pre==2;
if(!limit&&dp[pos][mod][pre]!=-1) //无上限并且已经访问过
return dp[pos][mod][pre];
int up=limit?a[pos]:9;//假设该位是2，下一位是3，如果现在算到该位为1，那么下一位是能取到9的，如果该位为2，下一位只能取到3
int tmp=0;
for(int i=0;i<=up;i++){
mod1=(mod*10+i)%13;//看是否能整除13，而且由于是从原来数字最高位开始算
pre1=pre;
if(pre==0&&i==1)pre1=1;//末尾不是1，现在加入1，标记末尾为1
if(pre==1&&i!=1)pre1=0;//末尾是1，现在加入的不是1，标记末尾不是1
if(pre==1&&i==3)pre1=2;//末尾是1并且加入的是3，标记含有13
tmp+=dfs(pos-1,mod1,pre1,limit&&i==up);//limit&&i==up，在最开始，取出的up是最高位，所以如果i比up小，那么i的下一位都可以到达9，而i==up了，最大能到达的就只有,a[pos-1]
}
if(!limit)
dp[pos][mod][pre]=tmp;
return tmp;
}
int solve(int x){
int pos=0;
while(x){
a[++pos]=x%10;
x/=10;
}
return dfs(pos,0,0,1);
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(a,0,sizeof(a));
memset(dp,-1,sizeof(dp));
printf("%d\n",solve(n));
}
return 0;
}