BZOJ1833: [ZJOI2010]count 数字计数

题目链接：bzoj1833

数位dp

考虑记忆化搜索，从0-9枚举当前统计答案的数字

记(dp[pos][cnt])表示当前做到第(pos)位时已经有(cnt)个符合条件的位上是所规定的数字

(limit)表示有无最高为限制

(zero)表示有无前导零（在此处前导零不合法）

(cnt)表示当前已经有多少位上的数是我当前所需要的数

大力转移即可

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxd=1000000007,N=100000;
const double pi=acos(-1.0);
typedef long long ll;
int num[20],len;
ll a,b,dp[20][20];

ll read()
{
	ll x=0,f=1;char ch=getchar();
	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
	return x*f;
}

ll dfs(int pos,int dig,int limit,int zero,ll cnt)
{
	if (!pos) return cnt;
	if ((!limit) && (!zero) && (dp[pos][cnt])) return dp[pos][cnt];
	ll ans=0;int i,final;
	if (limit) final=num[pos]; else final=9;
	for (i=0;i<=final;i++)
	{
		ans+=dfs(pos-1,dig,((limit) && (i==final)),((zero) && (i==0)),cnt+((i==dig) && ((!zero)||i))); 
	}
	if ((!limit) && (!zero)) dp[pos][cnt]=ans;
	return ans;
}

ll solve(ll x,int dig)
{
	len=0;
	memset(dp,0,sizeof(dp));
	while (x)
	{
		int tmp=x%10;x/=10;
		num[++len]=tmp;
	}
	return dfs(len,dig,1,1,0);
}

int main()
{
	a=read();b=read();
	int i;
	for (i=0;i<=9;i++) printf("%lld ",solve(b,i)-solve(a-1,i));
	return 0;
}