• （没学懂，待填坑）【动态规划】数位动态规划

    知识点

    一个讲得很好的blog：洛谷日报第84期：数字组成的奥妙——数位dp

    一 . 数位DP

    数位DP是与数位相关的一类计数类DP，一般用于统计区间[l,r]满足特定条件的数位元素个数。数位指个位、十位、百位、千位等，数位DP指的就是在数位上进行动态规划。数位DP实质上就是有策略的枚举，子问题求解后进行记忆化搜索即可。

    二 . 需要注意

    ① 记忆化 ②约束条件 ③高位前导0

    三 . 数位DP模板

    1. int dfs(int pos,int limit,int lead,int sum...各种限制)
    2. //pos表示填数到了第几位,limit表示有无上界限制,lead表示有无前导0 
    3. {
    4.     if(!pos)    return sum;//边界条件 
    5.     if(!limit&&!lead&&dp[pos][...]!=-1)//如果搜过并且没有上界限制和前导0,这一位可以随便填 
    6.     return dp[pos][...];//记忆化搜索 
    7.     int top=limit?a[pos]:9;
    8.     //如果前一位有限制（或填到了最高位）那么这一位不能超过a这一位的大小，否则0~进制数-1随便取 
    9.     int res=0; 
    10.     for(int i=0;i<=top;i++)
    11.     {
    12.         if(...)//限制条件 
    13.         res+=DFS(pos-1,limit&&(i==top),lead&&!i,...);
    14.       //如果所在位置位已经枚举到上界就把上界往后传,上一位有前导0而且这一位是0，那么下一位有前导0 
    15.     } 
    16.     if(!limit&&!lead)dp[pos][...]=res;
    17.         //因为如果枚举到上限则答案并不是这一位上所有的和，所以就不更新
    18. 	//着重分析这一句话：当有前导0或有上界限制时,下一位有不能填的数，而dp数组记录的是下一位能全部填0~9的数，所以不更新. 
    19.     return res; 
    20. }
    21.  
    22. int solve(int x)
    23. {
    24.     int num=0;//位数 
    25.     while(x)//这里是预处理出每一位数的上界 
    26.     {
    27.         a[++num]=x%10;
    28.         x=x/10;
    29.     }
    30.     return dfs(num,1,1,...);//是否有前导0和上界限制等，注意通常统计总和的时候，初始化为1 
    31. } 
    32. int main()
    33. {
    34.     cin>>l>>r;
    35.     cout<<solve(r)-solve(l-1)<
    36.     //可以先求1~r中满足限制的个数，再求1~l-1中满足限制的数的个数，相减即可得区间l~r的数据 
    37. }

     模板题

    1 .统计一个区间的数字的各个数位之和

    例题： 洛谷 P4999 烦人的数学作业 / 洛谷 P1836 数页码 

    思路：该题要求在区间内的数字各个数位相加所得的和，但是看数据范围1 \leqslant L \leqslant R \leqslant 10^{18}，可以发现数据范围很大，不能通过暴力做法，那么采用数位DP

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define ll long long 
    6. using namespace std;
    7. ll int T,l,r;
    8. const int maxn=1e7+5,mod=1e9+7;
    9. ll int dp[305][305],a[maxn];
    10. inline ll int read()
    11. {
    12. 	ll int x=0,f=1;
    13. 	char c=getchar();
    14. 	while(c<'0'||c>'9')
    15. 	{
    16. 		if(c=='-') f=-1;
    17. 		c=getchar();
    18. 	}
    19. 	while(c>='0'&&c<='9')
    20. 	{
    21. 		x=(x<<1)+(x<<3)+(c^48);
    22. 		c=getchar();
    23. 	}
    24. 	return x*f;
    25. }
    26.  
    27. inline ll int solve(ll int pos,ll int res,ll int limit)
    28. //pos表示填数到了第几位,limit表示有无上界限制,res表示最后的总数
    29. {
    30. 	if(!pos) return res; //到达边界退回res
    31. 	if(!limit && dp[pos][res]!=-1) return dp[pos][res];
    32. 	int top=limit?a[pos]:9; //记录当前数位最大值可以到多少
    33. 	ll int result=0;
    34. 	for(int i=0;i<=top;++i)
    35. 	{
    36. 		result=(result+solve(pos-1,res+i,limit && i==top))%mod;  
    37.         //当前区间各数数位和
    38. 	}
    39. 	if(!limit) dp[pos][res]=result;
    40. 	return result;
    41. }
    42.  
    43. inline ll int make(ll int x) //数位拆分
    44. {
    45. 	ll int num=0;
    46. 	while(x)
    47. 	{
    48. 	a[++num]=x%10;
    49. 	x/=10;	
    50. 	}
    51. 	return solve(num,0,1)%mod;
    52. }
    53.  
    54. int main()
    55. {
    56. 	T=read();
    57. 	memset(dp,-1,sizeof(dp));
    58. 	while(T--)
    59. 	{
    60. 		l=read(); r=read();
    61. 		printf("%lld\n",(make(r)-make(l-1)+mod)%mod);
    62.         //有个细节：如果取模后的结果相减是负数时，需要加上模数
    63. 	}
    64. 	return 0;
    65. }

     相关练习

    1 . SP17247 PR003004 - Digit Sum

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define ll long long 
    6. #define re register
    7. using namespace std;
    8. ll int n,l,r;
    9. const int maxn=1e7+5;
    10. ll int dp[305][305],a[maxn];
    11. inline ll int read()
    12. {
    13. 	ll int x=0,f=1;
    14. 	char c=getchar();
    15. 	while(c<'0'||c>'9')
    16. 	{
    17. 		if(c=='-') f=-1;
    18. 		c=getchar();
    19. 	}
    20. 	while(c>='0'&&c<='9')
    21. 	{
    22. 		x=(x<<3)+(x<<1)+(c^48);
    23. 		c=getchar();
    24. 	}
    25. 	return x*f;
    26. }
    27.  
    28. inline ll int solve(ll int pos,ll int res,ll int limit)
    29. {
    30. 	if(!pos) return res;
    31. 	if(!limit&&dp[pos][res]!=-1) return dp[pos][res];
    32. 	ll int top=limit?a[pos]:9;
    33. 	ll int cnt=0;
    34. 	for(re ll int i=0;i<=top;++i)
    35. 	{
    36. 		cnt+=solve(pos-1,res+i,limit&&(i==top));
    37. 	}
    38. 	if(!limit) dp[pos][res]=cnt;
    39. 	return cnt;
    40. }
    41.  
    42. inline ll int make(ll int x)
    43. {
    44. 	ll int num=0;
    45. 	while(x)
    46. 	{
    47. 		a[++num]=x%10;
    48. 		x/=10;
    49. 	}
    50. 	return solve(num,0,1);
    51. }
    52.  
    53. int main()
    54. {
    55. 	n=read();
    56. 	memset(dp,-1,sizeof(dp));
    57. 	while(n--)
    58. 	{
    59. 		l=read(); r=read();
    60. 		l=max(l-1,0ll);
    61.         //因为这里的l可以取到0，所以当l等于0时，需要特殊处理一下；
    62.         //因为0这里属于int型，强制转换long long类型
    63. 		printf("%lld\n",make(r)-make(l));
    64. 	}
    65. 	return 0;
    66. }

     2 . 洛谷 P4317 花神的数论题

    思路：由题得“已知 \text{sum}(i) 表示 i 的二进制表示中 1 的个数，求sum(1)∼sum(N) 的乘积”，先通过位运算统计数据中总共有几个1，再利用数位dp计算乘积。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define ll long long
    6. using namespace std;
    7. ll int n;
    8. const int maxn=1e7+5,mod=10000007;
    9. ll int a[maxn],dp[105][105];
    10. inline ll int read()
    11. {
    12. 	ll int x=0,f=1;
    13. 	char c=getchar();
    14. 	while(c<'0'||c>'9')
    15. 	{
    16. 		if(c=='-') f=-1;
    17. 		c=getchar();
    18. 	}
    19. 	while(c>='0'&&c<='9')
    20. 	{
    21. 		x=(x<<1)+(x<<3)+(c^48);
    22. 		c=getchar();
    23. 	}
    24. 	return x*f;
    25. }
    26.  
    27. inline int solve(ll int pos,ll int limit,ll int sum)
    28. {
    29. 	if(!pos) return max(sum,1ll); //统计乘积，赋值为1
    30. 	if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
    31. 	ll int top=limit?a[pos]:1; //最后的数字表示：进制减1
    32. 	ll int cnt=1; //因为统计乘积，赋值为1
    33. 	for(int i=0;i<=top;++i)
    34. 	{
    35. 	cnt=(cnt*solve(pos-1,limit&&(i==top),sum+i))%mod;
    36.         //记得取模运算
    37. 	}
    38. 	if(!limit) dp[pos][sum]=cnt;
    39. 	return cnt;
    40. }
    41.  
    42. inline ll int make(ll int x)
    43. {
    44. 	ll int num=0;
    45. 	while(x)
    46. 	{
    47. 		a[++num]=x & 1; //相当于x%2
    48. 		x=x>>1; //相当于x/2
    49. 	}
    50. 	return solve(num,1,0);
    51. }
    52.  
    53. int main()
    54. {
    55. 	memset(dp,-1,sizeof(dp));
    56. 	n=read();
    57. 	printf("%lld",make(n));
    58. 	return 0;
    59. }

    2 . 统计各个数在区间内的数位出现的次数

    例题： 洛谷 P2602 [ZJOI2010] 数字计数 / SP3928 MDIGITS - Counting Digits/洛谷 P1239 计数器 / UVA1640 统计问题 The Counting Problem （该题注意最后末位不能输出多余的空格）

     思路：由题得，需要统计各个数在区间内的数位上出现的次数。需要考虑有前导零的情况，要特别加上一个判断前导零的参数 lead。如果有前导零，且当前数码正好为 0，sum不变，然后接着扫下去，递归条件：sum+((i || !lead) && (i == num))。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define ll long long
    6. using namespace std;
    7. ll int l,r;
    8. const int maxn=1e6+5;
    9. ll int dp[105][105],a[maxn];
    10. inline ll int solve(ll int pos,ll int lead,ll int limit,ll int sum,int num)
    11. //pos用于记录存到了第几项，lead用于判断是否含有前导零，limit用于判断是否到达上界,sum用于记录总数
    12. //num用于记录当前寻找的是数字0~9中的哪一个
    13. {
    14. 	if(!pos) return sum;
    15. 	if(!limit&&!lead&&dp[pos][sum]!=-1) return dp[pos][sum];
    16. 	int top=limit?a[pos]:9;
    17. 	ll int res=0;
    18. 	for(ll int i=0;i<=top;++i)
    19. 	{
    20. 		res+=solve(pos-1,lead&&i==0,limit&&(i==top),sum+((i||!lead)&&(i==num)),num);
    21. 	}
    22. 	if(!limit&&!lead) dp[pos][sum]=res;
    23. 	return res;
    24. }
    25.  
    26. inline ll int make(ll int x,int no)
    27. {
    28. 	ll int num=0;
    29. 	while(x)
    30. 	{
    31. 		a[++num]=x%10;
    32. 		x/=10;
    33. 	}
    34. 	return solve(num,1,1,0,no);
    35. }
    36.  
    37. int main()
    38. {
    39. 	memset(dp,-1,sizeof(dp));
    40. 	while(scanf("%lld %lld",&l,&r)==2 && l!=0 && r!=0)
    41. 	{
    42. 		if(l>r) swap(l,r); //输入可能会存在后面的数比前面大的情况
    43. 		for(int i=0;i<=9;++i)
    44. 		{
    45. 			printf("%lld ",make(r,i)-make(l-1,i));
    46. 		}
    47. 		cout<
    48. 	}
    49. 	return 0;
    50. }

    3 . 有限制条件的区间数位问题

    例题 ：  洛谷 P2657 [SCOI2009] windy 数

     思路：由题得：“不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。”，那么存在限制条件：当前所在位的数字比它前一个数字至少大2或小2；以及当前数据是否含有前导0。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #define ll long long
    7. using namespace std;
    8. ll int l,r;
    9. const int maxn=1e7+5;
    10. ll int dp[305][305],a[maxn];
    11. inline ll int read()
    12. {
    13. 	ll int x=0,f=1;
    14. 	char c=getchar();
    15. 	while(c<'0'||c>'9')
    16. 	{
    17. 		if(c=='-') f=-1;
    18. 		c=getchar();
    19. 	}
    20. 	while(c>='0'&&c<='9')
    21. 	{
    22. 		x=(x<<3)+(x<<1)+(c^48);
    23. 		c=getchar();
    24. 	}
    25. 	return x*f;
    26. }
    27.  
    28. inline ll int solve(ll int pos,ll int lead,ll int limit,ll int check)
    29. //check用于统计当前位置的前一个数
    30. {
    31. 	if(!pos) return 1; //pos已经找到了最后一个，返回1
    32. 	if(!limit&&!lead&&dp[pos][check]!=-1) return dp[pos][check];
    33. 	ll int top=limit?a[pos]:9;
    34. 	ll int cnt=0;
    35. 	for(ll int i=0;i<=top;++i)
    36. 	{
    37. 		if(abs(i-check)<2) continue; //如果两数之间的差小于2，这两个点不满足条件，跳过
    38. 		if(lead&&i==0) cnt+=solve(pos-1,1,limit&&(i == top),-2);
    39.             //如果有前导0，下一位随意选择 
    40. 		else cnt+=solve(pos-1,0,limit&&(i == top),i);//如果没有前导0，继续向后搜
    41. 	}
    42. 	if(!limit&&!lead) return dp[pos][check]=cnt;
    43. 	return cnt;
    44. }
    45.  
    46. inline ll int make(ll int x)
    47. {
    48. 	ll int num=0;
    49. 	while(x)
    50. 	{
    51. 		a[++num]=x%10;
    52. 		x/=10;
    53. 	}
    54. 	return solve(num,1,1,-2); //注意最高位的下一位是没有数据的，赋值为-2进行标记
    55. }
    56.  
    57. int main()
    58. {
    59. 	memset(dp,-1,sizeof(dp));
    60. 	l=read(); r=read();
    61. 	printf("%lld",make(r)-make(l-1));	
    62. 	return 0;
    63. }

  • 相关阅读:
    MLAgents (0) Unity 安装及运行
    网络安全入门教程（非常详细）从零基础入门到精通，看完这一篇就够了。
    【数据结构】串
    BTCs打造区块链加营销广告数字流量新形式
    Windows 95 的辉煌诞生历史
    Linux下如何切换多版本Python
    第1关：构造函数与析构函数的实现
    Linux操作系统~基于systemV共享内存的进程间通信
    我在华为度过的 “两辈子”（学习那些在大厂表现优秀的人）
    perl删除目录下过期的文件
  • 原文地址：https://blog.csdn.net/gzkeylucky/article/details/126664804