数位动态规划 
    数位动态规划是求解一个大区间[L, R]中间满足条件Q的所有数字的个数(或者和,或其他)的一种方法。它通过分析每一位上的数字,一般用 dp[len][digit][...] 来表示状态“len位长的数字,最高位数字为digit所具有的xx特性”,利用记忆化搜索保存中间结果,从而加快求解速度。 
    通过求 f(n) 从0到n中满足条件Q的数字的个数,则所求的结果为 f(R) - f(L-1). 
    大多数数位dp都可以用一个DFS函数来进行记忆化搜索:

//len数字的位数,digit最高位的值,end_flag 表示digit是否是第len位(从低位向高位数,个位为第1位) 的范围边界
int Dfs(int len, int digit, bool end_flag){
//超出边界
if (len <= 0 || digit > 9 || digit < 0)
return 0;
//记忆化搜索,如果之前已经求出来了,则返回。注意这里要求 end_flag为false
if (!end_flag && dp[len][digit] != -1)
return dp[len][digit]; // 最简单情况看数字是否满足要求
if (len == 1)
return dp[len][digit] = xxx; //如果当前位是边界数字N对应位的最大值,则下一位的范围只能从0到边界数字N的下一位的最大值。否则为0 到 9
int end = end_flag ? bits[len - 2] : 9; int ans = 0;
for (int i = 0; i <= end; i++){
ans += Dfs(len - 1, i, end_flag && (i==end));
}
if (!end_flag) //digit不是第len位的最高范围,则可以将结果缓存
dp[len][digit] = ans;
return ans;
}

题目大意 
    给定一个区间[L, R],求区间内满足条件“数位上不含有4,且不含有62(62必须连续)”的数字的个数。

分析 
    直接套用模板

实现

#include<iostream>
#include<stdio.h>
using namespace std;
int dp[9][10];
int bits[8]; //用dfs进行记忆化搜索, dp[len][digit] 表示 len位数字,最高位为digit满足条件的个数. 这里对数字范围没有限制!
//搜索的时候,若要进行记忆化,需要 dp[len][digit]的结果对数字范围没有限制,因此需要判断 end_flag来决定是否进行记忆。 //len数字的位数,digit最高位的值,end_flag 表示digit是否是第len位(从低位向高位数,个位为第1位) 的范围边界
int Dfs(int len, int digit, bool end_flag){
//超出边界
if (len <= 0 || digit > 9 || digit < 0)
return 0;
//记忆化搜索,如果之前已经求出来了,则返回。注意这里要求 end_flag为false
if (!end_flag && dp[len][digit] != -1)
return dp[len][digit]; // 最简单情况看数字是否满足要求
if (len == 1)
return dp[len][digit] = (digit != 4);
if (digit == 4)
return dp[len][digit] = 0; //如果当前位是边界数字N对应位的最大值,则下一位的范围只能从0到边界数字N的下一位的最大值。否则为0 到 9
int end = end_flag ? bits[len - 2] : 9; int ans = 0;
for (int i = 0; i <= end; i++){
if (!(digit == 6 && i == 2)) //除去 62连续的情况
ans += Dfs(len - 1, i, end_flag && (i==end));
}
if (!end_flag) //digit不是第len位的最高范围,则可以将结果缓存
dp[len][digit] = ans;
return ans;
} //将数字n的各个位上的范围求出来,保存到bits数组中,返回数字n的长度
int Init(int n){
memset(bits, 0, sizeof(bits));
int k = 0;
while (n){
bits[k++] = n % 10;
n /= 10;
}
return k;
} int Solve(int n){
int len = Init(n);
//数字长度为len,则为了避免首位遍历从0到bits[len-1],给数字增加一个前导0。
//len + 1位,首位为0,且0是最高位的边界
int ans = Dfs(len + 1, 0, true);
return ans;
}
int main(){
int m, n;
memset(dp, -1, sizeof(dp));
while (scanf("%d %d", &m, &n)){
if (m == 0 && n == 0)
break;
int ret1 = Solve(m-1);
int ret2 = Solve(n);
int ret = ret2 - ret1;
printf("%d\n", ret);
}
return 0;
}

最新文章

  1. WCF学习之旅—第三个示例之一(二十七)
  2. 《使用Hibernate开发租房系统》内部测试笔试题
  3. CentOS 程序开机自启动方法总结
  4. int-&gt;string-------------c
  5. ecshop Admin后台删除(Ajxa删除,无跳转连接)
  6. Beta版本贡献比
  7. PLSQL导入Excel表中数据
  8. 【Android开发学习笔记】【第十课】运动事件 之——触摸屏
  9. ExtJs之文本框及数字输入
  10. frame,iframe,frameset用法和区别
  11. hdu_5877_Weak Pair(离散+DFS+树状数组)
  12. lvm创建 及 扩空 等相关
  13. Redis (非关系型数据库) 数据类型 之 list列表类型
  14. java基础知识学习--------之枚举类型(1)
  15. sqrtx-开平方
  16. altium designer中如何添加logo
  17. Python 文件内容读取
  18. MVC框架理解及优缺点
  19. Go_18: Golang 中三种读取文件发放性能对比
  20. openerp many2many

热门文章

  1. 2017年1月6日 星期五 --出埃及记 Exodus 21:32
  2. 微信网页获取openId
  3. iOS静态库和动态库的区别
  4. Cheatsheet: 2013 08.14 ~ 08.19
  5. [c/c++]linux下使用c/c++操作mysql
  6. SQL疑难杂症【1】解决SQL2008 RESTORE 失败问题
  7. POJ 3253 Fence Repair(修篱笆)
  8. C++学习网站
  9. 关于deferred
  10. 详解公用表表达式(CTE)