「CQOI2016」手机号码

蒟蒻我得好好学学数位DP。

传送门

洛谷P4124

BZOJ4521

题解

这题定义出来的数组有点长QwQ。

定义$F[pos][pre][pree][thr][fur][eig]$表示长度为$pos$，上一个数字为$pre$，上上个数字为$pree$，是/否出现过连续三个相同数字，是/否出现过4，是/否出现8，时的合法方案数。

然后写个记忆化DFS就好了。

代码

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
int A[15],len;LL L,R,F[15][11][11][2][2][2][2];
LL DFS(int pos,int pre,int pree,bool thr,bool fur,bool eig,bool lim)
{
	if(fur&&eig) return 0;
	if(pos==0) return thr;
	LL& ret=F[pos][pre][pree][thr][fur][eig][lim];
	if(ret!=-1) return ret;
	ret=0;
	int end=lim?A[pos]:9;
	for(int i=(pos==11?1:0);i<=end;i++)
		ret+=DFS(pos-1,i,pre,thr||(i==pre&&pre==pree),fur||i==4,eig||i==8,lim&&i==end);
	return ret;
}
LL Solve(LL n)
{
	if(n<10000000000ll) return 0;
	len=0;
	while(n){A[++len]=n%10;n/=10;}
	memset(F,-1,sizeof(F));
	return DFS(11,10,10,0,0,0,1);
}
int main()
{
	scanf("%lld%lld",&L,&R);
	printf("%lld\n",Solve(R)-Solve(L-1));
	return 0;
}