#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int t;
long long dp[][][];
long long l, r;
int shu[]; long long dfs(int len,..., bool shangxian)
{
if (len == )
return ...;
if (!shangxian && dp[len][...])
return dp[len][...]; //dp数组的内容应和dfs调用参数的内容相同,除了是否达到上限
long long cnt = ;
int maxx = (shangxian ? shu[len] : );
for (int i = ; i <= maxx; i++)
{
...;
cnt += dfs(len - ,..., shangxian && i == maxx);
}
if (!shangxian)
dp[len][...] = cnt;
return cnt;
} long long solve(long long x)
{
int k = ;
while (x)
{
shu[++k] = x % ;
x /= ;
}
return dfs(k,...,)
} int main()
{
memset(dp, , sizeof(dp));
scanf("%lld%lld", &l, &r); //有些题目其实并不需要用到long long
printf("%lld\n", solve(r) - solve(l - )); //只有满足区间减法才能用 //while (1);
return ;
}

数位dp是一种计数用的dp,一般就是统计一个区间[l,r]内满足一些条件数 的个数,所谓数位dp,字面意思就是在数位上dp。数位的含义:一个数有个位,十位,百位,千位···数的每一位就是数位。

之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式,使新的枚举方式满足dp的性质,然后记忆化即可。

两种不同的枚举:对于一个求区间[l,r]满足条件数的个数,最简单的暴力如下:

for(int i=l;i<=r;i++)
if(right(i))
ans++;

  然而这样枚举不方便记忆化,或者根本无状态可言。

最新文章

  1. 最新Mac OS X 10.12.1 安装cocoapods及使用详解
  2. AngularJS结合RequireJS做文件合并压缩的那些坑
  3. ArtDialog文档
  4. WebClient的异步处理
  5. linux添加环境变量
  6. Android NDK 【错误】The method loadLibrary(String) is undefined for the type Settings.Syste
  7. 学习Swift -- 构造器(中)
  8. animate基础
  9. 不要怂,就是GAN (生成式对抗网络) (六):Wasserstein GAN(WGAN) TensorFlow 代码
  10. Syntax error on tokens, delete these tokens.问题解决
  11. 12块钱搭建一个ss(包括一个免费服务器)
  12. dotnet core如何编译exe
  13. springboot连接数据库报错testWhileIdle is true, validationQuery not set
  14. Nginx ACCESS阶段 Satisfy 指令
  15. 关于djangorestframework相关源码分析
  16. android ViewStub简单介绍
  17. 卷积神经网络(CNN)张量(图像)的尺寸和参数计算(深度学习)
  18. memory cache 和 disk cache
  19. 使用jQuery+huandlebars遍历数组
  20. DOM文档对象模型

热门文章

  1. 【题解】IOI2005River 河流
  2. [洛谷P1892]团伙
  3. [51nod1791] 合法括号子段 DP
  4. 用JavaScript写一个类似PHP print_r的函数
  5. Dubbo入门介绍---搭建一个最简单的Demo框架
  6. HDU 2844 二进制优化的多重背包
  7. PropertiesConfiguration的用法
  8. synchronized ---- 作用
  9. java基础知识(二)-----多态和构造函数
  10. Topcoder SRM 607 div1题解