数位dp入门

发布于 2022-08-09  343 次阅读

碎碎念

今天来填之前的坑，顺便说说打工的那些事

《重生》大结局-Day7

因为前一天只写了剩下的15道普及-的题目

所以今天上午补完了最后6道普及题

下午去了海马体拍证件照，照骗啊照骗！

晚上被拉去同学聚会，被灌了酒qwq

那就不卷了叭！

总结一下这一周，43橙8黄，1场div3，1场div2

复健取得小成功！

《第一份兼职》Day1

白天教小朋友学C++，第一课最难的题目是求三个数的平均数（

值得一提，14个五年级中混进1个准大一，我教大一新生C++（

晚上教提高班写数位dp，emmm

我都不会，只能白天休息的时候学了

--------碎碎念到此结束，下面是正文（手动分割线）--------

白天现学的数位dp，总结一下叭

模板

#include<bits/stdc++.h>
using namespace std;
int n,cnt,a[20],dp[20][状态];
int dfs(int pos,状态,int limit)
{
	if(pos==0)return 是否符合要求;
	if(!limit && dp[pos][状态]!=-1)
		return dp[pos][状态];
	int x=limit?a[pos]:9;
	int ret=0;
	for(int i=0;i<=x;i++)
		ret+=dfs(pos-1,新状态,limit&&i==x);
	if(!limit)dp[pos][状态]=ret;
	return ret;
}
int main()
{
	memset(dp,-1,sizeof(dp));
	scanf("%d",&n);
	cnt=0;while(n)a[++cnt]=n%10,n/=10;
	printf("%d\n",dfs(cnt,状态,1));
	return 0;
}

HDU3652

求出含有13并能被13整除的数的个数

solution

状态储存上一位是否是1，有无出现过13，以及除以13的余数

//数位dp+记忆化搜索 
#include<bits/stdc++.h>
using namespace std;
int n,cnt,a[20],dp[20][20][5];
int dfs(int pos,int sum,int state,int limit)
{
	//state 0--剩余状态，1--上一位是1，2--出现过13
	if(pos==0)return state==2&&sum==0;//做完了 
	if(!limit && dp[pos][sum][state]!=-1)
		return dp[pos][sum][state];//无限制记忆化
	int x=limit?a[pos]:9;//能到达的最大位数
	int ret=0;
	for(int i=0;i<=x;i++)
	{
		int nxt_sum=(sum*10+i)%13;
		int nxt_state=state;
		if(state==0&&i==1)nxt_state=1;
		if(state==1&&i!=1)nxt_state=0;
		if(state==1&&i==3)nxt_state=2;
		//状态转化 
		ret+=dfs(pos-1,nxt_sum,nxt_state,limit&&i==x);
	}
	if(!limit)dp[pos][sum][state]=ret;
	//无限制记忆化 
	return ret;
}
int main()
{
	memset(dp,-1,sizeof(dp));
	while(scanf("%d",&n)!=EOF)
	{
		cnt=0;while(n)a[++cnt]=n%10,n/=10;
		//初始化 
		printf("%d\n",dfs(cnt,0,0,1));
	}
	return 0;
}

HDU4734

定义一个数第i位为ai的权值为ai*2i-1

一个数的权值为其所有位的权值之和

求出权值不超过某给定权值的数的个数

solution

状态储存距离零还需要多少权值

//数位dp+记忆化搜索 
#include<bits/stdc++.h>
using namespace std;
int T,a,b,cnt,t[20],p[20],dp[20][5000];
int dfs(int pos,int sum,int limit)
{
	if(sum<0)return 0;
	if(pos==0)return 1;
	if(!limit && dp[pos][sum]!=-1)
		return dp[pos][sum];
	int x=limit?p[pos]:9;
	int ret=0;
	for(int i=0;i<=x;i++)
		ret+=dfs(pos-1,sum-i*t[pos],limit&&i==x);
	if(!limit)dp[pos][sum]=ret;
	return ret;
}
int f(int x)
{
	int ret=0,ct=1;
	while(x)
	{
		ret+=t[ct]*(x%10);
		x/=10,ct++;
	}
	return ret;
}
int main()
{
	memset(dp,-1,sizeof(dp)),t[1]=1;
	for(int i=2;i<=10;i++)t[i]=t[i-1]*2;
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		scanf("%d%d",&a,&b);
		cnt=0;while(b)p[++cnt]=b%10,b/=10;
		printf("Case #%d: %d\n",i,dfs(cnt,f(a),1));
	}
	return 0;
}