HDU3652 B-number

B-number

题意：
求1-n(<=1e9)中是13的倍数且包含“13”的个数。多组数据。

数位DP

#include<bits/stdc++.h>
using namespace std;
int n;
int dat[15],cnt;
int f[13][11][2][15];

int dfs(int pos,int pre,bool limit,bool hav,int lj)
{
	if(pos==0)return f[pos][pre][hav][lj]=hav&&(lj==0);
	if(!limit && f[pos][pre][hav][lj]!=-1)return f[pos][pre][hav][lj];
	int up=limit?dat[pos]:9;
	int ans=0;
	for(int i=0;i<=up;++i)
	{
		ans+=dfs(pos-1,i,limit&&(i==up),hav||(pre==1&&i==3),(lj*10+i)%13);
	}
	if(!limit)f[pos][pre][hav][lj]=ans;
	return ans;
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		cnt=0;
		memset(f,-1,sizeof f);
		while(n)
		{
			++cnt;
			dat[cnt]=n%10;
			n/=10;
		}
		printf("%d\n",dfs(cnt,0,1,0,0));
	}
	return 0;
}