http://acm.hdu.edu.cn/showproblem.php?pid=2089
题意:
求区间内不包含4和连续62的数的个数。
思路:
简单的数位dp模板题。给大家推荐一个好的讲解博客。http://blog.csdn.net/mosquito_zm/article/details/75226543
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn=+; int l,r;
int dp[maxn][];
int dig[]; int dfs(int pos, int pre, int state, int limit)
{
if(pos==-) return ;
if(!limit && dp[pos][state]!=-) return dp[pos][state];
int up=limit?dig[pos]:;
int tmp=;
for(int i=;i<=up;i++)
{
if(i==) continue;
if(pre== && i==) continue;
tmp+=dfs(pos-,i,i==,limit&&i==dig[pos]);
}
if(!limit) dp[pos][state]=tmp;
return tmp;
} int solve(int x)
{
int pos=;
while(x)
{
dig[pos++]=x%;
x/=;
}
return dfs(pos-,-,,);
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d%d",&l,&r))
{
if(l== && r==) break;
memset(dp,-,sizeof(dp));
int ans=solve(r)-solve(l-);
cout<<ans<<endl;
}
return ;
}