牛客：处女座和小姐姐（三）(数位dp)

传送门：处女座和小姐姐（三）

题意：给个区间，求区间中包含六的数的个数（long long 型）

思路：数位DP，还是dalao的模板好，先求出0~n中不包含六的数，再减一下。

WA：记忆化搜索（dfs），否则TLE...

/***********************************************/
int a[20];
ll dp[20];//记录前i位中没有6的个数 

ll dfs(int cur,bool limit) 
{						
	if(cur==0) return 1;
	if(!limit && dp[cur]!=-1) return dp[cur];
	ll ans=0;
	int cu=limit?a[cur]:9;
	
	for(int i=0;i<=cu;i++)
	{
		if(i!=6 ) 	//显然如果前面几位的情况中有出现6，那么就不会继续下去 
			ans+=(dfs(cur-1,limit & (i==a[cur]) ));
	}
	if(!limit) dp[cur]=ans;//还是那个记忆化 
	return ans;
}

ll solve(ll x)
{
	int cut=0;
	while(x){
		a[++cut]=(x%10);
		x/=10;
	}
	return dfs(cut,1);
}

int main()
{
	ll a,b;
	mem1(dp);
	cin>>a>>b;
	cout<<b-a+1-solve(b)+solve(a-1)<<endl;
	return 0;
}