数位dp
2022/9/5 23:22:59
本文主要是介绍数位dp,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数位dp
目录- 数位dp
- 简介
- 题
- 同类分布
- \(\text{Balanced Number}\)
简介
数位 \(dp\) 是一种在数位上进行的 \(dp\),通常用于解决值域 \([L,R]\) 中有几个数满足条件,且 \([L,R]\) 极大 (如 \(1\le L\le R\le 1e18\)) 的问题,这时我们就会在数位上进行 \(dp\),问题规模变为 \(\lg R\) 的
数位 \(dp\) 就是一次考虑数的每一位,且从高到低枚举 (因为高位限制低位的取值范围)
我们通常用 \(lim\) 变量来表示更高的数位是否都与 \(R\) 的对应位相同
如:\(R=123\),若前面两位取的 \(12\),那第 \(3\) 位只能为 \(0\sim 3\),若不是,则可以取 \(0\sim 9\)
我们通常使用记忆化搜索来实现数位 \(dp\)
数位 \(dp\) 模板:
inline ll dfs(int pos,int sum,int lim,...){ if(!pos) {...}//数字填完了 if(~f[pos][sum][rm][lim]) return f[pos][sum][rm][lim];//记忆化 int mx=lim?a[pos]:9;//当前位最大是多少 ll res=0; for(int i=0;i<=mx;++i) res+=dfs(pos+1,sum+i,lim&(i==mx),...);//填数 f[pos][sum][rm][lim]=res;//记忆化 return res; }
题
https://vjudge.net/contest/513260
同类分布
以这道题为例说明一下数位 \(dp\) 的常规解法
记搜的时候我们记录 \(4\) 个变量:
\(pos\):当前搜到第几位
\(sum\):各位数字之和
\(rm\):原数对当前枚举的模数 \(mod\) 取模的结果
\(lim\):前几位是否和原数相同
这题我们的思路是枚举模数 \(mod\),然后通过记搜记录有几个符合要求,并统计答案
#include<bits/stdc++.h> using namespace std; #define ll long long int len,a[20],mod; ll l,r,f[20][180][180][2]; inline ll dfs(int pos,int sum,int rm,int lim){ if(pos>len&&!sum) return 0; if(pos>len) return (rm==0&&sum==mod); if(~f[pos][sum][rm][lim]) return f[pos][sum][rm][lim]; int mx=lim?a[len-pos+1]:9; ll res=0; for(int i=0;i<=mx;++i) res+=dfs(pos+1,sum+i,1ll*(1ll*rm*10ll+i)%mod,lim&(i==mx)); f[pos][sum][rm][lim]=res; return res; } inline ll solve(ll x){ len=0; do{ a[++len]=x%10; x/=10; }while(x); ll res=0; for(mod=1;mod<=9*len;++mod){ memset(f,-1,sizeof(f)); res+=dfs(1,0,0,1); } return res; } signed main(){ cin>>l>>r; cout<<solve(r)-solve(l-1); }
\(\text{Balanced Number}\)
这篇关于数位dp的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行