标签为 [数位DP] 的文章

BZOJ4521手机号码

题目大意 不包含4或8,且至少包含3个连续数字的数为合法的手机号码。问l,r区间内合法的手机号码有几个? Solution 这题是很显然的数位DP。当然,如果直接套dp方程可能会显得麻烦,所以还是用记忆化搜索。思路直接描述有点困难,所以直接看代码和注释。 代码 #include<cstdio>; #include<algorithm>; #include<cstring>; using namespace std; long long l,r; long long num[20][10][10][2][2][2]; int a[20]; long long dfs(int len,int p1,int ......