题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2089
题目:
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。
输出n~m中不包含不吉利数字4和62的数字个数
解题思路:
数位dp模版题,考虑前缀和[n,m]=[m,0]-[n-1,0]即solve(m)-solve(n-1)。
dp[pos][sta]即dp[pos][pre],pos为下标,pre为pos前一位的数字,这道题中pre分为6和非6,即sta可以对应的设置为1和0两种状态。
limit为限制条件,即判断是否达到上限。
基础优化:
if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
if(!limit) dp[pos][sta]=sum;
比如统计1~568之间不含62的个数,若当百位为0时的个数为sum,计入dp[pos][sta]中,那么在百位为1,2,3,4(未达到百位上限5)时也可知对应的答案分别为sum,这样的话直接return sum即可,不必再做复杂重复的调用,以免超时。
ac代码:
#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 1000005
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
ll dp[20][3],a[20];
ll dfs(ll pos,ll pre,ll sta,bool limit)
{
if(pos==0) return 1;
if(!limit && dp[pos][sta]!=-1) return dp[pos][sta];
ll sum=0;
ll up=limit?a[pos]:9;
for(ll i=0;i<=up;i++)
{
if(i==4)continue;
if(pre==6&&i==2) continue;
sum+=dfs(pos-1,i,i==6,limit && i==a[pos]);
}
if(!limit) dp[pos][sta]=sum;
return sum;
}
ll solve(ll x)
{
ll i=0;
while(x)
{
a[++i]=x%10;
x/=10;
}
return dfs(i,-1,0,true);
}
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0) break;
memset(dp,-1,sizeof(dp));
printf("%lld\n",solve(m)-solve(n-1));
}
return 0;
}