HDU2089 不要62 —— 数位DP

时间：2023-02-15 13:42:14

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089

不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 47943    Accepted Submission(s): 18165

Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
1 100
0 0
Sample Output
80
Author
qianneng
Source

题目的一般形式：

求 [ L, R ] 范围内满足限制条件的值的个数。

而 [ L, R ]  = [ 0 , R ] - [ 0, L-1 ] ，所以做法就是分别求出 在R范围内满足条件的个数t1， 和 在L-1范围内满足条件的个数t2。

则 ans = t1 - t2。

数位DP（记忆化搜索）：

数组：dp[pos][s1][s2][s3……]

pos表示当前位， s1 、s2 ……表示限制条件，维数的个数即限制条件的个数。

比如：dp[pos][s] 表示当前位为pos， 先前状态为s的满足条件的个数。

注意：若先前状态的某个限制条件对后续状态没有影响，那么该限制条件就无需记录了。（例如：HDU3253）

题解：

求一段区间内不含有“4”以及“62”的数的个数。经典的数位DP。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const double eps = 1e-;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e6+;

 int dp[][], digit[];

 int dfs(int pos, int state, int lim)    //pos为当前位， status为上一位的状态（是否为6）， lim是否仍处于上限

 {

     if(!pos) return ;

     if(!lim && dp[pos][state] != -) return dp[pos][state];

     int ret = ;

     int maxx = lim?digit[pos]:;    //当前位可取的最大值

     for(int i = ; i<=maxx; i++)

     {

         //如果遇到4或者62， 则跳过

         if( i== || (state && i==) )   continue;

         ret += dfs( pos-, i==, lim&&(i==maxx) );

     }

     if(!lim) dp[pos][state] = ret;  //如果没有处于上限，则记录下来。

     return ret;

 }

 int solve(int n)

 {

     int len = ;

     while(n)

     {

         digit[++len] = n % ;

         n /= ;

     }

     return dfs(len,,);

 }

 int main()

 {

     int n, m;

     memset(dp,-,sizeof(dp));

     while(scanf("%d%d",&m,&n) && (m||n) )

     {

         cout<< solve(n)-solve(m-) <<endl;

     }

     return ;

 }

相关文章