数位DP是我的噩梦。

现在初三了，却没AC过数位DP的题目。

感觉数位DP都是毒瘤……

题目

hdu不用登录也可以进去，所以就不把题目copy到这里来了。

题目大意

求区间[n,m][n,m][n,m]中，不含有444和626262的数的个数。

---

解析

数位DP的难点主要在于不能出界。

因为这个东西，我被卡了不知道多少年……

先不要想出界，那么显然，状态可以这么设：

设fi,jf_{i,j}fi,j​表示做到第iii位，并且这一位为jjj的方案数。

方程显然

	if (j!=4 && !(j==6 && k==2))

		f[i][j]+=f[i-1][k];

所以我们可以先预处理出fff数组。

对于区间[n,m][n,m][n,m]，类似前缀和，我们可以将其转化成求[1,x][1,x][1,x]。

接下来就是最毒瘤的出界问题了。

比如x=314x=314x=314

那么f2,0,f2,1,f2,2f_{2,0},f_{2,1},f_{2,2}f2,0​,f2,1​,f2,2​可以计入贡献，因为前面的数字不管怎么变，都必定不会出界。

但是f2,3f_{2,3}f2,3​是不可以直接计入贡献的。

所以咋办？

我们可以继续下一位，计算x=14x=14x=14时的贡献，当然，要记录一下上一次最后的数，在计入贡献前要先判断是否合法。

因为我们计算的都是小于xxx的贡献，所以在计算之前我们要先将xxx加一

具体见下面的代码。

---

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define MAXM 1000000

int n,m;

int f[10][10];

int pow10[10];

void init();

int getans(int);

int main(){

	pow10[0]=1;

	for (int i=1;i<=9;++i)

		pow10[i]=pow10[i-1]*10;

	init();

	do{

		scanf("%d%d",&n,&m);

		if (n==0 && m==0)

			return 0;

		printf("%d\n",getans(m)-getans(n-1));

	}

	while (1);

	return 0;

}

void init(){

	for (int i=0;i<=9;++i)

		f[0][i]=(i!=4);//i!=4时就为1

	for (int i=1;i<=6;++i)

		for (int j=0;j<=9;++j){

			if (j==4)

				continue;

			for (int k=0;k<=9;++k)

				f[i][j]+=f[i-1][k];

			if (j==6)

				f[i][j]-=f[i-1][2];//将j==6和k==2不合法的贡献减掉

		}

}

int getans(int x){

	x++;//因为下面的算法计算的是小于x的贡献，所以要先x++

	if (x<0)

		return 0;

	int res=0,w=log10(x);//w为x的位数

	for (int i=w,lst=0;i>=0;--i){

		int s=x/pow10[i]%10;//求出第i为的贡献

		for (int j=0;j<s;++j)

			res+=f[i][j];//将小于s的贡献全部加上（因为前面的数怎么变都不可能越界）

		if (lst==6 && 2<s)

			res-=f[i][2];//同样将不合法的贡献减去

		if (s==4 || lst==6 && s==2)//如果这个时候出现不合法的情况，那么后面的都是不合法的，直接退出

			break;

		lst=s;

	}

	return res;

}

–

总结

数位DP最难的地方就是判断出界。

所以我们应该从高位到低位逐个判断。

保证范围小于边界。