[Hdu3652]B-number（数位DP）

Description

题目大意：求小于n是13的倍数且含有'13'的数的个数。

(1 <= n <= 1000000000)

Solution

数位DP，题目需要包含13，且被13整除，所以状态应该多2个，

(F[i][j][k])表示位数为i，余数为j，包含13状态为k的方案数

其中k(0,1,2)，2表示已经包含13，1表示上一个为1，否则为0

记忆化打法

Tips:

1. 数组k维要开到3
2. DP数组只算一次，只需开始初始化一次
3. 计算转移的k时的顺序

Code

#include <cstdio>
#include <cstring>

int n,d[15],f[15][15][3];

int dfs(int p,int mo,int exi,int lim){
	int &tmp=f[p][mo][exi],r=0;
	if(!p) return exi==2&&!mo;
	if(!lim&&tmp!=-1) return tmp;	
	
	int mx=lim?d[p]:9;
	for(int i=0;i<=mx;++i){
		int t=0;
		if(exi==2) t=2;//必须先判，否则错解
		else if(exi==1&&i==3) t=2;
		else if(i==1) t=1;
		r+=dfs(p-1,(mo*10+i)%13,t,lim&&(i==mx));
	}
	return lim?r:tmp=r;
}

int main(){
	memset(f,-1,sizeof(f));
	while(~scanf("%d",&n)){
		int len=0;
		while(n){
			d[++len]=n%10;
			n/=10;
		}
		printf("%d
",dfs(len,0,0,1));
	}
	return 0; 
}