数位dp模版(dp)
2024-09-25 20:33:22
#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++;
然而这样枚举不方便记忆化,或者根本无状态可言。
最新文章
- 最新Mac OS X 10.12.1 安装cocoapods及使用详解
- AngularJS结合RequireJS做文件合并压缩的那些坑
- ArtDialog文档
- WebClient的异步处理
- linux添加环境变量
- Android NDK 【错误】The method loadLibrary(String) is undefined for the type Settings.Syste
- 学习Swift -- 构造器(中)
- animate基础
- 不要怂,就是GAN (生成式对抗网络) (六):Wasserstein GAN(WGAN) TensorFlow 代码
- Syntax error on tokens, delete these tokens.问题解决
- 12块钱搭建一个ss(包括一个免费服务器)
- dotnet core如何编译exe
- springboot连接数据库报错testWhileIdle is true, validationQuery not set
- Nginx ACCESS阶段 Satisfy 指令
- 关于djangorestframework相关源码分析
- android ViewStub简单介绍
- 卷积神经网络(CNN)张量(图像)的尺寸和参数计算(深度学习)
- memory cache 和 disk cache
- 使用jQuery+huandlebars遍历数组
- DOM文档对象模型