bzoj1026
题目描述：求A到B之间不含前导0且相邻两位数字的差至少为2的数的个数。
输入格式：两个整数，表示A和B。
输出格式：一个整数，表示答案。
输入样例：
1 10
输出样例：
9
解析：数位DP的入门题，dp[pos][pre]表示搜到第pos位，上一位是pre的数的个数。注意一下前导0就没多大问题。
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 6 int a, b, dp[15][10], bit[15], cnt; 7 8 int dfs(int pos, int lead, int limit, int pre) { 9 if (!pos) return dp[pos][pre] = 1; 10 if (limit && lead && ~dp[pos][pre]) return dp[pos][pre]; 11 int len = limit ? 9 : bit[pos], ans = 0; 12 for (int i = 0; i <= len; ++ i) { 13 if (abs((double)i - pre) < 2) continue; //别问我为什么abs要强转成double，不这么打在bzoj上会ce QAQ 14 int tmp = i; 15 if (i == 0 && !lead) tmp = -3; //对前导0特殊处理 16 ans += dfs(pos - 1, lead || i > 0, limit || i < len, tmp); 17 } 18 if (lead && limit) dp[pos][pre] = ans; 19 return ans; 20 } 21 22 int solve(int x) { 23 cnt = 0; 24 while (x) { 25 bit[++ cnt] = x % 10; 26 x /= 10; 27 } 28 memset(dp, -1, sizeof(dp)); 29 return dfs(cnt, 0, 0, -3); 30 } 31 32 int main() { 33 scanf("%d %d", &a, &b); 34 printf("%d", solve(b) - solve(a - 1)); 35 return 0; 36 }
转载于:https://www.cnblogs.com/Gaxc/p/9920415.html
