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 ;
}