动态规划——数位-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划——数位。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划——数位DP

”某一区间“满足某种性质

技巧1：[x,y]=f[y]-f[x-1];

技巧2：树;

模板如下：

//框架模板数位dp
#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int f[N][10];  //f[i][j]:长度为i，以j开头的满足条件的数的个数
void init()//解决实质方法 初始化f
{

}

int dp(int x)//解决区间问题 
{
	if(x==0)return 0;
	vector<int> nums;
	while(x)nums.push_back(x%10),x=x/10;
	
	int res=0;
	int last=0;//用来记录前面有关系的一个性质 
	
	for(int i=nums.size()-1;i>=0;i--)
	{
		int x=nums[i];
        //先处理左边分支
        
        //继续讨论处理右边分支，条件判断，更新last，最后i=0时候res更新
		
	}
	
	return res;
	
}
int main()
{
	init();
	cin>>a>>b; 
	cout<<dp(b)-dp(a-1)<<endl;
	return 0;
 }

例1：度的数量

动态规划——数位,ACM,动态规划,代理模式,算法
分析：

#include<bits/stdc++.h>
using namespace std;
int x,y,k,b;
const int N=35;
int f[N][N];
void init()//组合数——杨辉三角形
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(!j)f[i][j]=1;
			else f[i][j]=f[i-1][j-1]+f[i-1][j];
		}
	}
}
int dp(int x)
{
	if(!x)return 0;
	
	vector<int> nums;
	while(x)nums.push_back(x%b),x=x/b;
	
	int res=0;
	int last=0;//记录前面的位数占用的1
	
	for(int i=nums.size()-1;i>=0;i--)
	{
		int x=nums[i];
		if(x)//为了防止超出区间只有x不为0才有选择 
		{
			res+=f[i][k-last];//如果当前位为0 
			if(x>1)//如果当前位选择为1
			{
				res+=f[i][k-last-1];
				break; 
			} 
			else//当前本来就为1，就需要继续讨论 
			{
				last++;
				if(last>k)break; 
			}
		}
		if(i==0&&last==k)res++;//最右侧分支上的1 
	 } 
	 return res; 
}
int main()
{
	cin>>x>>y>>k>>b;
	init();
	cout<<dp(y)-dp(x-1)<<endl;
	return 0;
}

例2、数字游戏

动态规划——数位,ACM,动态规划,代理模式,算法
分析：

动态规划——数位,ACM,动态规划,代理模式,算法

#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int f[N][N];//f[i][j]为长度为i，且以j开头的的有多少个不降数 
void init()//动态规划预处理
{
	for(int i=0;i<=9;i++)f[1][i]=1;
	for(int i=2;i<=N;i++) 
	{
		for(int j=0;j<=9;j++)
		{
			for(int k=j;k<=9;k++)
			{
				f[i][j]+=f[i-1][k];
//				cout<<f[i][j]<<endl;
			}
		}
	}
}

int dp(int x)
{
	if(x==0)return 1;
	vector<int> nums;
	while(x)nums.push_back(x%10),x=x/10;
	
	int res=0;
	int last=0;//用来记录上一位数字 
	
	for(int i=nums.size()-1;i>=0;i--)
	{
		int y=nums[i];
		for(int j=last;j<y;j++)//左边分支的处理
		{
			res+=f[i+1][j]; 
		} 
		if(y<last)break;
		last=y;//右边分支的处理
		if(i==0)res++;//右边最后分支的处理
	}
	return res;
	
}
int main()
{e
	init();
	while(cin>>ea>>b)
	{
		cout<<dp(b)-dp(a-1)<<endl;
	}
	return 0;
 }

例3、 Windy数

动态规划——数位,ACM,动态规划,代理模式,算法

如果要求dp（1567），由于第一个根节点的分叉左枝干是从1开始，那么就等于0-999都没有算进res里面

好好理解f的含义，例如f[3] [9]表示最高位为9长度为3 满足条件的windy数的个数，那么是9_ _,900–999中的个数

#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int f[N][10];   
void init()//解决实质方法 
{
	for(int i=0;i<=9;i++)f[1][i]=1;
	for(int i=2;i<=N;i++)
	{
		for(int j=0;j<=9;j++)
		{
			for(int k=0;k<=9;k++)
			{
				if(abs(j-k)>=2)
				f[i][j]+=f[i-1][k];
			}
		}
	} 
}

int dp(int x)//解决区间问题 
{
	if(x==0)return 0;
	vector<int> nums;
	while(x)nums.push_back(x%10),x=x/10;
	
	int res=0;
	int last=-2;//用来记录前面有关系的一个性质 
	
	for(int i=nums.size()-1;i>=0;i--)
	{
		int y=nums[i];
		for(int j=i==nums.size()-1;j<y;j++)
		{
			if(abs(j-last)>=2)
			res+=f[i+1][j];
		}
		if(abs(y-last)>=2)last=y;
		else break;
		if(!i)res++;
		
	}
	//特殊处理000——的情况 ，也就是一开始少算了前导0的部分区间
	for(int i=1;i<nums.size();i++)
	{
		for(int j=1;j<=9;j++)
		res+=f[i][j];
	}

	return res;
	
}
int main()
{
	init();
	cin>>a>>b; 
	cout<<dp(b)-dp(a-1)<<endl;
	return 0;
 }

4、数字游戏

动态规划——数位,ACM,动态规划,代理模式,算法

#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=35;
int M;
int f[N][10][100];  //数长为i，以j为开头，每个数字之和模为t 
void init()//解决实质方法 
{
	memset(f,0,sizeof(f));
	for(int i=0;i<=9;i++)f[1][i][i%M]++;
	
	for(int i=2;i<N;i++)
	{
		for(int j=0;j<=9;j++)
		{
			for(int t=0;t<=M-1;t++)
			{
				for(int k=0;k<=9;k++)
				{
					f[i][j][t]+=f[i-1][k][((t-j)%M+M)%M];
				//	cout<<f[i][j][t]<<endl;
				}
			}
		}
	}
}

int dp(int x)//解决区间问题 
{
	if(x==0)return 1;
	vector<int> nums;
	while(x)nums.push_back(x%10),x=x/10;
	
	int res=0;
	int last=0;//用来记录前面有关系的一个性质 
	
	for(int i=nums.size()-1;i>=0;i--)
	{
		int y=nums[i];
		for(int j=0;j<y;j++)//处理左边的分支 
		{
			res+=f[i+1][j][(M+-last)%M];
		}
		last=(last+y)%M;
		if(i==0&&last==0)res++;
		
	}

	return res;
	
}
int main()
{
	while(cin>>a>>b>>M)
	{
	
	init();
	cout<<dp(b)-dp(a-1)<<endl;
}
	return 0;
 }

5、不要62

动态规划——数位,ACM,动态规划,代理模式,算法

有些该有的条件不可省略

#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=10;
int f[N][10];  //数长为i，以j为开头
//f[i][j]+=f[i-1][k],如果j为2,k就不会为6 
void init()//解决实质方法 
{
	for(int i=0;i<=9;i++)f[1][i]=1;
	f[1][4]=0;
	for(int i=2;i<=N;i++)
	{
		for(int j=0;j<=9;j++)
		{
			if(j==4)continue;
			for(int k=0;k<=9;k++)
			{
				if(k==4||(j==6&&k==2))continue;
				f[i][j]+=f[i-1][k];
			}
		}
	 } 
}

int dp(int x)//解决区间问题 
{
	if(x==0)return 1;
	vector<int> nums;
	while(x)nums.push_back(x%10),x=x/10;
	
	int res=0;
	int last=0;//用来记录前面有关系的一个性质 
	
	for(int i=nums.size()-1;i>=0;i--)
	{
		int y=nums[i];
		for(int j=0;j<y;j++)
		{
			if(last==6&&j==2)continue;
			res+=f[i+1][j];
		}
		if(last==6&&y==2)break;
		if(y==4)break;
		last=y;
		if(!i)res++;
	} 
	return res;
	
}
int main()
{
	init();
	while(~scanf("%d %d",&a,&b),a&&b)
	{ 
		cout<<dp(b)-dp(a-1)<<endl;
	}
	return 0;
 }

6、

[USACO06NOV] Round Numbers S

如果一个正整数的二进制表示中， $0$ 的数目不小于 $1$ 的数目，那么它就被称为「圆数」。

例如， $9$ 的二进制表示为 $1001$ ，其中有 $2$ 个 $0$ 与 $2$ 个 $1$ 。因此， $9$ 是一个「圆数」。

请你计算，区间 $[l, r]$ 中有多少个「圆数」。

一行，两个整数 $l, r$ 。

一行，一个整数，表示区间 $[l, r]$ 中「圆数」的个数。

2 12

【数据范围】

对于 $100\%$ 的数据， $1\le l,r\le 2\times 10^9$ 。

【样例说明】

区间 $[2, 12]$ 中共有 $6$ 个「圆数」，分别为 $2, 4, 8, 9, 10, 12$ 。

#include<bits/stdc++.h>
using namespace std;
int a,b;
const int N=50;
int f[N][2][N];//数长为i,圆数的个数
//f[i][0][j]+=f[i][0][j-1] 
//f[i][j][p][t]=f[i-1][k1][p-j][t-t*i0]
//第三维为数字之和的模，第四维为证书之和的模 

void init()//解决实质方法 
{
	f[1][0][1]=1;
	f[1][1][0]=1; 
	for(int i=2;i<N;i++)
	{
		for(int j=0;j<=1;j++)
		{
			for(int k=i;k>=0;k--)//表示的是0的个数 
			{
				if(j)f[i][j][k]=f[i-1][0][k]+f[i-1][1][k];
				if(k&&!j) f[i][j][k]=f[i-1][0][k-1]+f[i-1][1][k-1];
			
			}
		}
	}
}

int dp(int x)//解决区间问题 
{
//	if(x==0)return 1;
	vector<int> nums;
	while(x)nums.push_back(x%2),x=x/2;
	
	int res=0;
	int last=0;//用来记录前面有关系的一个性质 
	int l=nums.size();
	
	
	for(int i=nums.size()-2;i>=0;i--)
	{
		int y=nums[i];
		if(y)//y为1———
		{
			for(int j=l-last;j>=(l+1)/2-last;j--)
			{
				if(j<=i+1)res+=f[i+1][0][j];
			}
		}
		if(!y)last++;
		if(!i&&last>=(l+1)/2)res++;
		
	} 
	for(int i=1;i<l;i++){
		for(int j=i;j>=(i+1)/2;j--)
			res+=f[i][1][j];
	}
	return res;
	
}
int main()
{
	init();
	cin>>a>>b;
	cout<<dp(b)-dp(a-1)<<endl;

	return 0;
 }

7、花神花神的数论题

众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。

话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。花神的题目是这样的：设 $\text{sum}(i)$ 表示 $i$ 的二进制表示中 $1$ 的个数。给出一个正整数 $N$ ，花神要问你 $\prod_{i=1}^{N}\text{sum}(i)$ ，也就是 $\text{sum}(1)\sim\text{sum}(N)$ 的乘积。

一个正整数 $N$ 。

一个数，答案模 $10000007$ 的值。

对于 $100\%$ 的数据， $1\le N\le 10^{15}$ 。

运用快速幂的方法文章来源地址https://www.toymoban.com/news/detail-762144.html

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll x;
const ll N=55;
ll f[N][2][N];//长度为i，以j开头的，1的个数为k的数有多少个 
ll mod=10000007;
void init()//解决实质方法 
{
	f[1][0][0]=1;
	f[1][1][1]=1; 
	for(int i=2;i<N;i++)
	{
		for(int j=0;j<=1;j++)
		{
			for(int k=i;k>=0;k--)//表示的是1的个数 
			{
				if(j&&k)f[i][j][k]=f[i-1][0][k-1]+f[i-1][1][k-1];
				if(!j) f[i][j][k]=f[i-1][0][k]+f[i-1][1][k];
			}
		
		}                            
	}
}
ll quick_mi(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		b=b/2;
		a=a*a%mod;
	}
	return res;
}
ll dp(ll x)//解决区间问题 
{
//	if(x==0)return 1;
	vector<int> nums;
	while(x)nums.push_back(x%2),x=x/2;
	
	ll res=1;
	int last=1;//用来记录前面有关系的一个性质 
	int l=nums.size(); 
	for(int i=nums.size()-2;i>=0;i--)//从第二位分支开始  
	{
		int y=nums[i];
		if(y)//y为1———
		{
			for(int j=0;j<=i;j++)
			{
				res=(res*quick_mi(j+last,f[i+1][0][j])%mod)%mod;
			}
		}
		if(y)last++;//增加1的个数 
		
		if(!i)res=(res*last)%mod;
		
	} 
	for(int i=1;i<l;i++){
		for(int j=1;j<=i;j++)
			res=(res*quick_mi(j,f[i][1][j])%mod)%mod;
	}
	return res;
	
}
int main()
{
	init();
	cin>>x;
	cout<<dp(x)<<endl;

	return 0;
 }

到了这里，关于动态规划——数位的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！