数位dp
2019-08-26 05:36:14来源:博客园 阅读 ()
数位dp
基础
对于一类问题:求给定区间内,满足给定条件的数的个数。一般情况下,这类问题通常采用暴力枚举求解:
for(int i=l;i<=r;++i)
if(right(i)) ++ans;
很显然,当给定区间过大时,无法直接用朴素的方法求解。而所求的限定条件往往与数位有关,例如数位之和、指定数码个数、数的大小顺序分组等等。此时我们就需要利用数位的性质,设计log级别复杂度的算法。
解决这类问题最基本的思想就是“逐位确定”,有时求解这类问题时还需要做预处理,而预处理的过程即可视作数位dp。
简单而言,数位dp就是在给定的区间内,利用限定条件,逐位暴力枚举的算法。
对于数位dp,可通过简单的分析进行了解。
我们假设给定一个r=312。对于数位dp的过程,也就是从最高位即百位起,顺次枚举0-9。
但是很显然,以百位3为例,枚举时数字最大不能超过3。同时当百位为3时,十位最大不能超过1;当百位为3,十位为1时,个位最大不能超过2。其他限定情况下也以此类推。所以在实际的运用中,需要用一个布尔变量limit记录这一情况。
另一方面,数位dp中,对于问题的求解,通常是:
printf("%d\n",solve(l)-solve(r-1));
所以不管左端点是多少,百位一定会枚举到0,可是这样前导零可能会影响计数(视题目而定),所以通常情况下还会用一个布尔变量lead记录具体情况。
lead和limit一样,当前面已经不存在前导零or最大值限定时,是不必再继续限定的。
这样就得到了数位dp最基本的模板:
int dfs(int pos,int sta,bool lead,bool limit)
//pos即枚举到的位数;sta起到记录作用,一般情况下是记录上一位的数值,也有可能根据题意记录如4的个数5的个数
//lead记录前导零;limit记录数值的限定
{
if(pos==-1) return 1;//也就是位数由大到小枚举退出的边界
if(!limit&&!lead&&dp[pos][sta]!=-1) return dp[pos][sta];//情况已经记录时返回,节省时间
int up=limit?a[pos]:9,ans=0;//确定可枚举到的最大数
for(int i=0;i<=up;++i)
{
//判断条件
}
if(!limit&&!lead) dp[pos][sta]=ans;//记忆化,存储节省时间
return ans;
}
int solve(int x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}//确定每一位的最大值限定
return dfs(pos-1,-1,true,true);
}
int main()
{
memset(dp,-1,sizeof(dp));
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",solve(b)-solve(a-1));
}
要注意的是,dfs的四个变量并不一定会用到,也有可能更多,视情况而定。
同时,solve中的拆分也可能是二进制的情况。
例题
例题1 SCOI2009 windy数
比较典型的数位dp例题,要注意前导零的情况,可以直接套板子。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int a[15],dp[15][15]; int dfs(int pos,int sta,bool lead,bool limit) { if(pos==-1) return 1; if(!limit&&!lead&&dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:9,ans=0; for(int i=0;i<=up;++i) { if(!lead&&abs(i-sta)<2) continue; if(lead&&i==0) ans+=dfs(pos-1,sta,lead,limit&&i==a[pos]); else ans+=dfs(pos-1,i,lead&&i==0,limit&&i==a[pos]);//注意limit是要根据前几位更改所以要limit&&i==a[pos] } if(!limit&&!lead) dp[pos][sta]=ans; return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,-1,true,true); } int main() { memset(dp,-1,sizeof(dp)); int a,b; scanf("%d%d",&a,&b); printf("%d\n",solve(b)-solve(a-1)); }
例题2 POJ 3252 Round Numbers
这里就要注意sta存储的不再是上一位的值而是0比1多的值,但是因为可能会出现0比1少也就是负数的情况,而数组下标不能是负数,所以初始值就要根据题目设为32。
又因为是二进制,所以solve也会有一定的更改。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int a[15],dp[15][15]; int dfs(int pos,int sta,bool lead,bool limit) { if(pos==-1) return 1; if(!limit&&!lead&&dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:9,ans=0; for(int i=0;i<=up;++i) { if(!lead&&abs(i-sta)<2) continue; if(lead&&i==0) ans+=dfs(pos-1,sta,lead,limit&&i==a[pos]);//当有前导零时会对结果产生影响所以sta不会更改 else ans+=dfs(pos-1,i,lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead) dp[pos][sta]=ans; return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,-1,true,true); } int main() { memset(dp,-1,sizeof(dp)); int a,b; scanf("%d%d",&a,&b); printf("%d\n",solve(b)-solve(a-1)); }
原文链接:https://www.cnblogs.com/ninecities/p/11390441.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:时间复杂度
- 如何0基础学习C/C++? 2020-06-06
- 复习C++语法--基础篇 2020-05-27
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- C++基础 学习笔记五:重载之运算符重载 2020-04-23
- C++基础 学习笔记四:重载之函数重载 2020-04-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash