第一个数位dp的题 做的老困难了。。。只是好歹是做出来了 迈出了第一步。。
对大牛来说这样的题都是小case
ps:新上一个记忆化方法 一些绕弯的题里用dfs好想些
代码例如以下:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[8][3];
/*
dp[i][0]无不吉利数字
dp[i][1]无不吉利数字且高位为2
dp[i][2】有不吉利数字
*/
void Init()
{
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
int i;
for(i = 1; i <= 8; ++i)
{
dp[i][0]=dp[i-1][0]*9-dp[i-1][1]; //在最高位加上除了4之外的9个数字，可是可能在2之前加了6
dp[i][1]=dp[i-1][0]; //在原先不含不吉利数字的最高位加2
dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1]; //在已经有不吉利数字最高位加随意数字。或者在无吉利数字前加4，或者在2前面加4
}
}
int Solve(int n)
{
int ls[9],len = 0,i,ans,tmp = n,flag = false;
while(n)
{
ls[++len] = n%10;
n /= 10;
}
ans = ls[len+1] = 0;
for(i = len; i; --i)
{
ans += dp[i-1][2]*ls[i];
if(flag) //高位已出现4或62 后面随意加
ans += dp[i-1][0]*ls[i];
if(!flag && ls[i] > 4) //高位有出现4的可能
ans += dp[i-1][0];
if(!flag && ls[i+1] == 6 && ls[i] > 2)//高位有出现62的可能
ans += dp[i][1];
if(!flag && ls[i] > 6)
ans += dp[i-1][1];
if(ls[i] == 4 || (ls[i+1] == 6 && ls[i] == 2)) //出现4或62
flag = 1;
}
return tmp - ans;
}
int main()
{
int n,m;
Init();
while(~scanf("%d %d",&n,&m) && n && m)
{
printf("%d\n",Solve(m)-Solve(n-1));//[m,n]区间
}
return 0;
}
//记忆化
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[8][3],digit[8];
/*
hav =
2 不含不吉利数字
1 不含不吉利数字 最高位6
0 含不吉利数字
high:前面是否出现高位(即当前位置可不能够随便填
*/
int dfs(int pos,int hav,bool high)
{
if(pos == -1) return hav == 0;
if(!high && ~dp[pos][hav]) return dp[pos][hav];
int en = high? digit[pos]: 9;
int i,ans = 0,nhav;
for(i = 0; i <= en; ++i)
{
nhav = hav;
if((hav == 1 && i == 2) || i == 4) nhav = 0;
else if(hav == 2 && i == 6) nhav = 1;
else if(hav == 1 && i != 6) nhav = 2;
ans += dfs(pos-1,nhav,high && i == en);
}
if(!high) dp[pos][hav] = ans;
return ans;
}
int Solve(int x)
{
memset(dp,-1,sizeof(dp));
int len = 0,tmp = x;
while(x)
{
digit[len++] = x%10;
x /= 10;
}
return tmp - dfs(len-1,2,1);
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m) && n)
{
printf("%d\n",Solve(m) - Solve(n-1));
}
return 0;
}