HDU-2089(不要62)

题目链接

HDU 2089

思路

数位DP，我的理解就是求一个区间内满足一些条件的数的个数。
通过记忆化搜索和动态规划的方法让我们能够更快速的得到答案。

代码模板

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool limit)
//pos是当前枚举的位置，pre是针对这道题的前面是否出现6，然后sta指的是当前的状态
//for循环内放入限制条件
{
	if(pos==-1)return 1;
	if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta];
	int up = limit?a[pos]:9;
	int tmp = 0;
	for(int i=0;i<=up;i++)
	{
		if(pre==6&&i==2)continue;
		if(i==4)continue;
		tmp += dfs(pos-1,i,i==6,limit&&i==a[pos]);
	}
	if(!limit)dp[pos][sta]=tmp;
	return tmp;
}
int solve(int x)
{
	int pos = 0;
	while(x)
	{
		a[pos++]=x%10;
		x/=10;
	}
	return dfs(pos-1,-1,0,true);
}
int main()
{
	int n,m;
	while(~scanf("%d %d",&n,&m)&&(n||m))
	{
		memset(dp,-1,sizeof(dp));
		printf("%d\n",solve(m)-solve(n-1));
	}
	return 0;
}