HDU 2089的类似题(62换成了38) 数位dp解释

2018-01-28 (更新于2021-10-10) / Algorithm / #HDU #nowcoder #数位dp

链接 来源:牛客网

杭州人称傻乎乎的人为62,而嘟嘟家这里没有这样的习俗。

相比62,他那里的人更加讨厌数字38,当然啦,还有4这个

数字!所以啊,嘟嘟不点都不想见到包含38或者4的数字。

每次给出一个区间[n,m],你能找到所有令人讨厌的数字吗?

输入描述:

多组输入输出; 输入的都是整数对n、m(0<n≤m<1000000), 如果遇到都是0的整数对,则输入结束。

输出描述:

对于每次的输入 输出全部令人讨厌的数的个数

示例1 输入

1 100 0 0

输出

20

#include <iostream>
#include <cstring>
using namespace std ;
const int len = 7 ;
int dp[8][10] , bit[8] ;//全局变量初始为0,dp[x][y]数组表示长为x的以y打头的所有数中“合法”数的个数,
// 注意首位为0的数也看作x位,例如0123看作4位数,
// 原因:如果不考虑以0开头的数那么dp[3][3] = dp[2][9] + dp[2][8] + ...+ dp[2][2] + dp [2][1] + dp[1][9] + dp[1][8] + ... + dp[1][2] + dp[1][1]
// 若把所有一位数看作以0开头的2位数则实际上dp[3][3] = dp[2][9] + dp[2][8] + ...+ dp[2][2] + dp [2][1] + dp[2][0]
// 所以认为dp[x][0] = dp[x-1][0...9]
// 我们只需要把dp[2][0...9]这些加起来就好了
int n , m ;

void Get_dp() {
	dp[0][0] = 1 ;
	for ( int i = 1 ; i <= len ; ++i )//长度i从1到7
		for ( int j = 0 ; j <= 9 ; ++j )//数值j从0到9
			if ( j != 4 )//排除j等于4的情况
				for ( int k = 0 ; k <= 9 ; ++k )//第二个数值k从0到9
					if ( !( j == 3 && k == 8 ) )//排除j,k为3,8的情况
						dp[i][j] += dp[i - 1][k] ;//i从1开始所以i-1不会越界且由于是全局变量默认值为0,所以免去了对i-1是否越界的讨论

					/**
					* 从长为1位的数,开头的数从0到9,填表
					* 状态转移方程:
					* dp[x][y] = 0;	若y==4
					* 			dp[x-1][0...9];	若y!=3(相当于在所有x-1位的合法数前面加了个不是3的数,肯定也是合法数)
					* 			dp[x-1][0...9] - dp[x-1][8];	若y==3则要排除掉第二位为8的情况
					*/
}

int solve( int n ) {//根据表来得出从1到n(实际上没有包括n,因为下面有一句for ( int j = 0 ; j < bit[i] ; ++j )用的小于号,我们先不考虑这细节)的所有合法数的个数
	memset( bit , 0 , sizeof( bit ) ) ;//将n分解放入bit数组中
	int top = 0 ;//(从n的底位到高位倒序放入)
	while ( n ) {
		bit[++top] = n % 10 ;
		n /= 10 ;
	}

	int ans = 0 ;//保存所有合法数个数
	for ( int i = len ; i >= 1 ; --i ) {//i从数的最高位开始向下
		for ( int j = 0 ; j < bit[i] ; ++j )
			if ( !( bit[i + 1] == 3 && j == 8 ) )
				ans += dp[i][j] ;//排除上一位是3且这一位以8开头的情况
		if ( bit[i] == 4 || ( bit[i + 1] == 3 && bit[i] == 8 ) )
			break ;//若这一位是4则跳出循环
	}
	/**
	* 这里举个例子解释一下:
	* 假设输入n为243
	* 那么我们应该将1...243分解成		000...199		200...239 		240...242				243
	* 对应一下其实就是				dp[3][0...1]	dp[2][0...3]	dp[1][0...2]			dp[0][]恒为0(所以代码中不管数字n是否合法都没有考虑到,最终返回值其实是1...n-1的所有合法数个数)
	* 注解							(1)				(2)				(3)不合法,之后的也是		(4)不合法
	* 
	* (1)从最高位开始
	* (2)00...39中的所有合法数前面加一个2还是合法数
	* (3)0...2的前面加上一个4出问题了!!,所有的0...2中的合法数变得不合法,应该排除,接下来所以位的分解前面也会加上4,所以直接跳出循环
	*	if ( bit[i] == 4 || ( bit[i + 1] == 3 && bit[i] == 8 ) )
	* 		break ;//若这一位是4则跳出循环
	* (4)这里为什么单独分开来?提示:“小于”号“<”
	* 
	* 其实这些分法都是受到了上面的:
	* for ( int j = 0 ; j < bit[i] ; ++j )
	* 的影响(注意小于号),也就是按照这条语句来分的
	* 需要仔细想想
	*/
	return ans ;
}

int main() {
	Get_dp() ;//打表
	while ( cin >> n >> m && ( n || m ) )
		cout << m - n + 1 - ( solve( m + 1 ) - solve( n ) ) << endl ;
	return 0 ;
}