admin 管理员组文章数量: 887021
数位
这几天在看数位dp，总算稍微有一丢丢的看明白了，所以就来浅浅的分享一下吧！！！
文章目录
- 概况
- 基本思想
- 模板
- 注意：
- 例题
概况
数位dp主要是来求一个区间满足条件的个数的
比如 ：从10到20之间求1的个数。显然有11个，但是在做题的时候范围会很大像是1e18 之类的 ，所以通常的方法就很容易超范围所以数位dp是一个不错的选择。
基本思想
假设范围是n~m，我们可以通过dp求出1到n的满足条件的个数，在求出1到m满足条件的个数。两者相减就是范围内满足条件的个数。
long long int n,m;cin>>n>>m;cout<<solve(m)-solve(n-1)<<endl;
大体的思想就是，我们通过n分解成每一位数，从最高位开始枚举。
比如：234；
如果最高位枚举2的话十位则枚举的范围是（0~3）
如果最高位枚举的是（0 ~ 1）时，十位则枚举范围是（0 ~ 9）之后随着位数以此类推
2 3 42 3 (0~4)2 (0~2) (0~9)(0~1) (0~9) (0~9)
采用这个枚举方式进行记忆化搜索；
模板
数位dp感觉还是蛮容易想的如果你知道模板
ll dp[20][20]; // 为了记忆化搜索储存
ll arr[100]; //为了统计每一位数的值，所以数组大小不用太大。
//pos为位数，就是dfs执行到一个数哪一位。
//sta是状态，状态不同的题状态不一样
// land为前导0 比如从0到12345 则1就表示成00001,这些0就是前导0
//limit是为了记录上一位的值是不是最大值，好为了判断这一位值的范围 比如123 十位如果执行到2 则各位范围只能是0~3，如果十位是（0~1）则各位可以是（0~9）
ll dfs(int pos,int sta,int land,int limit)
{ // land为1则这一位是前导0// limit为1则表示执行到这个数这一位的最大值if(pos==-1)return 1;//表示一个数执行完成了 返回值不一定是1，根据题目会有所改变。if(!limit&&!land&&dp[pos][sta]!=-1)return dp[pos][sta]; //记忆化存储 枚举到当前位置 pos，状态为 sta 的数量，dp 值保存的是满足条件数的个数int up=limit?arr[pos]:9;//枚举这一位的上界long long int ret=0;for(int i=0;i<=up;i++){if()。。。。。if(....)。。。。。 ret+=dfs(pos-1,sta(/*状态的变形*/),land&&i==0,limit&&i==arr[pos]);//进行搜索}if(!land&&!limit) dp[pos][sta]=ret;//搜索完成储存数目return ret;}ll solve(ll x)
{int pos=0;while(x)//分解位数{arr[pos++]=x%10; //储存上界的每一位x/=10;}return dfs(pos-1,0,1,1);
}int main()
{ll n,m;cin>>n>>m;memset(dp ,-1,sizeof dp); //进行初始化cout<<solve(m)-solve(n-1）<<" ";cout<<endl;}
注意：
（1）前导0的使用方法
当初看的时候就是感觉这个前导0好像在这串代码里没啥用的样子。但是确实有用（hhhh） 上面说了我们给每一个数都在前面加了前导0让他和最大数的位数相同。这里前导0有可能扰乱我们的基数
比如：我们来计数（1~123）的0的个数
1则就相当于001，1前面的前导0 就会扰乱我们对0的计数。
（2）我们的状态需要自己定义，这还是一个难点对我来说，还有就是那个pos==-1返回的值不是一成不变的根据题意稍作修改。
（3）还要注意dp数组还有里面的个别变量会超过int类型的最大值。所以需要把它们设置成 long long
例题
（1）P4999 烦人的数学作业
求给定区间内每个数的每一位数之和的和；
比如 123~124=1+2+3+1+2+4
代码：
#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define MAXN 100005
using namespace std;long long int n,m,f[408][408],arr[1000109],c[100009],sum[409],dp[408][408];
long long int mod=1e9+7;
long long dfs(long long int pos,long long int sum,int limit)
{if(pos==-1)return sum;if(!limit&&f[pos][sum]>=0)return f[pos][sum];int up=limit?arr[pos]:9;int temp=0;for(int i=0;i<=up;i++)temp=(temp+dfs(pos-1,sum+i,limit&&i==up))%mod;if(!limit)f[pos][sum]=temp;return temp;
}long long int solve(long long int x)
{long long int pos=0;while(x){arr[pos++]=x%10;x/=10;}return dfs(pos-1,0,1)%mod;
}
int main()
{int t;cin>>t;memset(f,-1,sizeof f);while(t--){long long int n,m;cin>>n>>m;cout<<(solve(m)-solve(n-1)+mod)%mod<<endl;}
}（2）P2602 [ZJOI2010]数字计数
给定范围内出现（0~9）的次数
代码：
#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define MAXN 100005
#define ll long long
using namespace std;ll dp[20][20][20];
ll arr[10000];
ll dfs(int pos,int sta,int land,int limit,int number)
{if(pos==-1)return sta;if(!limit&&!land&&dp[pos][number][sta]!=-1)return dp[pos][number][sta];int up=limit?arr[pos]:9;long long int ret=0;for(int i=0;i<=up;i++){if(land&&i==0)ret+=dfs(pos-1,sta,land&&i==0,limit&&i==arr[pos],number);elseret+=dfs(pos-1,sta+(number==i),land&&i==0,limit&&i==arr[pos],number);}if(!land&&!limit) dp[pos][number][sta]=ret;return ret;}ll solve(ll x,int number)
{int pos=0;while(x){arr[pos++]=x%10;x/=10;}return dfs(pos-1,0,1,1,number);
}int main()
{ll n,m;cin>>n>>m;memset(dp ,-1,sizeof dp);for(int i=0;i<10;i++)cout<<solve(m,i)-solve(n-1,i)<<" ";cout<<endl;
}
这两个题一个使用了前导0，一个 没有使用，细细品味！！！
本文标签： 数位
版权声明：本文标题：数位 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687016657h55595.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论