当前位置: 代码迷 >> 综合 >> HDU2089-数位DP
  详细解决方案

HDU2089-数位DP

热度:33   发布时间:2024-01-18 01:08:17.0
//dp[i][0]:第i位没有不吉利数字的个数
//dp[i][1]:第i位没有不吉利数字但最高位数字为2
//dp[i][2]:第i位有不吉利数字
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std ;
int m , t ;
int dp[10][3] ;
int num[10] ;
void Init()
{memset(dp, 0 , sizeof(dp) ) ;dp[0][0] = 1 ;for(int i = 1 ; i <= 6 ; i ++){dp[i][0] = 9 * dp[i-1][0] - dp[i-1][1];//最高位加上不含4的9个数字的状况,但因为会放6,所以要减去前一种开头为2的情况dp[i][1] = dp[i-1][0] ;//开头只放了2dp[i][2] = dp[i-1][2]*10 + dp[i-1][1] + dp[i-1][0] ;//已经含有的前面放什么数都可以,或者是放一个4,或者是在2前面放6}
}
int solve(int n)//计算0-n之间有多少个不吉利数字
{int temp = n ;int ans = 0 ;int len = 0 ;while(n != 0){num[++len] = n % 10 ;n /= 10 ;}num[len+1] = 0 ;int flag = 0 ;//标记当前是否有不吉利数字,这个数字一定不吉利for(int i = len ; i >= 1 ; i --){ans += dp[i-1][2] * num [i] ;if(flag) ans += dp[i-1][0]*num[i] ; //如果有不吉利数字if(!flag && num[i] > 4) ans += dp[i-1][0] ;//第i位为4if(!flag && num[i+1] == 6 && num[i]>2) ans += dp[i][1] ;//第i位为2if(!flag && num[i] > 6) ans += dp[i-1][1] ;//可能有62if(num[i] == 4 ||(num[i+1]==6 && num[i]==2)) flag = 1;}return temp - ans ;
}
int main()
{while(scanf("%d%d",&m,&t)!= EOF,m+t){Init();//solve()在处理过程中,没有考虑数字n是否不吉利cout << solve(t+1)-solve(m) << endl ;}
}