题目
Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。
Idea
这是一道数位DP的入门题目. 所谓数位DP, 就是考虑每一个数位(digit)的出现方式, 通过记忆化的方式初步降低复杂度, 来达到优化程序的目的.
枚举的方式
最简单的方法如下: for i=[l..r] if(ok(i)) ans++;
但是在高中的时候做排列组合题目的时候我们有另一种方式: 把每一位当作独立的对象, 然后做就行了.
于是我们考虑最高位开始, 比如上限是\(4145\), 那么我们考虑从高到低, 一位一位枚举的时候会发生什么:
(1) 第一位的时候就必须是\([1..4]\)而不应该是别的. 此外, 在\([1..3]\)的时候和\([4]\)的时候后续的状态也是不一样的. 因此我们需要记录当前是否选择了最高位(用bool
类型lim
表示, 表示存不存在限制).
(2) 另外, 注意到如果第一位选择了0, 那么就打开了前导0选项. (用bool
类型zero
表示, 表示现在是不是还是处于前导零的选项).
因此我们有伪代码:
DFS(int x(位置), ...(状态) ,bool lim, bool zero ){
if(x==0) return 0;
检查记忆化的结果
up = lim?(数组的第x位代表的数字):9
ans = 0
for i=0..up{
分情况讨论, 并且执行
ans +=
dfs(
位置: x-1,
状态: ...(状态转移),
下一位是否受限制: lim && i==数组的第x位代表的数字,
下一位是否是前导零: zero && i==0,
)
}
计算完存档
}
需要注意, 这个性质是不是存在前缀和的性质. (相减)
因此, 我们来看这个问题.
Code
#include <bits/stdc++.h>
using namespace std;
#define F(i, a, b) for(int i=(a); i<=(b);i++)
#define Fd(i, a, b) for(int i=(a);i>=(b);i--)
#define int long long
int f[15][15][15][15];
int num[15]={0};
int dfs(int x, int pre, int lim, int zero){
// printf("x=%d pre=%d lim=%d\n", x, pre, lim);
if(x==0) return 1;
if(f[x][pre][lim][zero]!=-1) return f[x][pre][lim][zero];
int up = lim ? num[x]:9;
int ans = 0;
F(i, 0, up){
if(i==2 && pre == 6) continue;
if(i==4) continue;
ans += dfs(x-1, i, lim && (i==up), i==0&&zero);
}
// printf("ans = %d\n", ans);
f[x][pre][lim][zero]=ans;
return ans ;
}
int solve(int x){
memset(f,-1,sizeof f);
int pos=0;
while(x){
num[++pos]=x%10;
x/=10;
}
return dfs(pos,-1,1,1);
}
signed main(){
int le,ri;
while(cin>>le>>ri && le+ri){
memset(f,-1,sizeof f);
cout<<solve(ri)-solve(le-1)<<"\n";
}
return 0;
}
标签:pre,不要,zero,int,lim,HDU2089,62,&&,ans
From: https://www.cnblogs.com/augpath/p/16915260.html