DP问题之数位统计DP

DP问题之数位统计DP DP问题之数位统计DP

代码基本都一样，有固定的模板，last数组一般存储前缀信息,dp(n)表示0~n中满足条件的数的个数

P338. 计数问题

last记录前面u的个数

#include
#include
#include
#include
using namespace std;
const int N=15;
int f[N][10][10];
void init(){
	for(int i=0;i<=9;i++) f[1][i][i]=1;
	for(int i=2;i nums;
	while(n){
		nums.push_back(n%10);
		n/=10;
	}
	int res=0;
	int last=0;
	for(int i=nums.size()-1;i>=0;i--){
		int x=nums[i];
		res+=last*x*pow(10,i);//求左分支,计算前面的u的个数 
		for(int j=(i==nums.size()-1);j>l>>r,l||r){
		if(l>r) swap(l,r);
		for(int i=0;i<=9;i++){
			printf("%d ",dp(r,i)-dp(l-1,i));
		}
		printf("n");
	}
	return 0;
}

P1081. 度的数量

当最高位为0~ a n − 1 a_{n-1} an−1​-1时，后面的数可以随便填都不会大于N，所以此时我们可以直接用组合数算出方案数，而当最高位等于 a n − 1 a_{n-1} an−1​时，后面的数就不能随便乱填了，此时我们就需要更进一步划分，具体见下图

本质其实也是闫氏DP分析法，只是集合划分看成一棵树更清楚，组合数的求法用 C a b = C a − 1 b + C a − 1 b − 1 C_a^b=C_{a-1}^{b}+C_{a-1}^{b-1} Cab​=Ca−1b​+Ca−1b−1​(见组合数)，这题每一位只能填0或1，一旦填了别的数就一定不合法了，要break掉，last记录前面已经确定的数中1的个数

#include
#include
#include
using namespace std;
const int N=35;//位数最多30位 
int f[N][N];
int K,B;
void init(){
	for(int i=0;i nums;
	while(n){
		nums.push_back(n%B);
		n/=B;
	}
	int res=0;
	int last=0;
	for(int i=nums.size()-1;i>=0;i--){//倒序枚举,相当于从原数的最高位开始枚举 
		int x=nums[i];
		//之所以不写下面那种循环是因为我们并不能填0~x-1所有数,只能填0/1 
		//for(int j=0;j1){//此时才能枚举当前这一位填1 
				if(K-last-1>=0) res+=f[i][K-last-1];
				break;//因为x>1,所以此时右分支一定不存在了  
			}
			else{//x=1,要继续往下递归 
				last++;
				if(last>K) break; 
			}
		}
		if(i==0&&last==K) res++;//最下面那个右分支 
	}
	return res;
}
int main(){
	init();
	int l,r;
	scanf("%d%d%d%d",&l,&r,&K,&B);
	printf("%d",dp(r)-dp(l-1));
	return 0;
}

P1082. 数字游戏

last记录上一位数是几，因为第一位数随便是几，所以last一开始只要给一个小于等于0的数即可，但因为之后循环要用到last，所以last只能初始化0

#include
#include
#include
using namespace std;
const int N=15;
int f[N][N];
void init(){
	for(int i=1;i nums;
	while(n){
		nums.push_back(n%10);
		n/=10;
	}
	int res=0;
	int last=0;
	for(int i=nums.size()-1;i>=0;i--){
		int x=nums[i];
		for(int j=last;j>l>>r){//只能用cin 
		printf("%dn",dp(r)-dp(l-1));
	}
	return 0;
}

P1083. Windy数

本题f[i][j]定义为所有最高位是j，且一共有i位的windy数的个数

last和上题一样，记录上一位的数，但为了让第一位随便填，last要初始化为一个跟0~9任何一个数之差大于等于2的数
包含前导0的意思其实就是它的位数比较低，但我们做dp时规定它是n位数，因此前面只能补0，比如13满足windy数，如果我们规定它是4位数时(N=4)，那么就会变成0013，不再满足windy数，答案就是这么漏的，因此我们在最后要把1~n-1位的windy数通过f[i][j]特殊计算出来
一开始初始化时要把前导零的情况算进去，因为20是在f[2][2]里面的，f[2][2]是由f[1][0]转移得到的，因此f[1][0]也要初始化为1

#include
#include
#include
using namespace std;
const int N=11;
int f[N][N];
void init(){
	for(int i=0;i=2){
					f[i][j]+=f[i-1][k];
				}
			}
		}
	}
}
int dp(int n){
	if(!n) return 0;
	vector nums;
	while(n){
		nums.push_back(n%10);
		n/=10;
	}
	int res=0;
	int last=-2;
	for(int i=nums.size()-1;i>=0;i--){
		int x=nums[i];
		for(int j=(i==nums.size()-1);j=2){
				res+=f[i+1][j];
			}
		}
		if(abs(x-last)>=2) last=x;
		else break;//不存在右分支 
		if(i==0) res++;
	}
	//特殊处理位数为1~n-1中有前导零的数 
	for(int i=1;i 
P1084. 数字游戏 II 
f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模N结果为k的数的个数
 状态转移： 因为第i位已经是j，且所有数字之和模N为k，所以我们考虑第i-1位，假设第i-1位数字是x，由于j已经知道，那么剩下的i-1位数字之和模N的结果就是(k-j)%N，可表示为f[i-1][x][(k-j)%N]
 last存储前面已确定的所有数的和
 
#include
#include
#include
#include
using namespace std;
const int N=15,M=100;
int f[N][10][M];
int P;
int mod(int x,int y){//为了得到正余数 
	return (x%y+y)%y;
}
void init(){
	memset(f,0,sizeof(f));
	for(int i=1;i nums;
	while(n){
		nums.push_back(n%10);
		n/=10;
	}
	int res=0;
	int last=0;
	for(int i=nums.size()-1;i>=0;i--){
		int x=nums[i];
		for(int j=0;j>l>>r>>P){
		init();
		printf("%dn",dp(r)-dp(l-1));
	}
	return 0;
}
 
P1085. 不要62 (未看) 
P1086. 恨7不成妻 (未看)					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714841.html