【动态规划】数位dp

典中典 P2602 数字计数

递推实现

首先计算0000…~9999…之间数字出现次数

• 递推角度$dp[i]=dp[i-1]\times 10+10^{i-1},dp[i]是i位数的计数$

  • $10^{i-1}$是最高位上出现次数
  • $dp[i-1]\times 10$是其他低位上出现次数

• 排列组合角度$dp[i]=i\times 10^i/10$

  • i个0递增到i个9 所有字符出现$i\times 10^i$
  • 再$/10$分配到每个数字上

然后分普通情况和逼近情况计算0~x的计数，使用前缀和

const int N=16,INF=1e9+10;
int cnta[10],cntb[10];
int dp[N],ten[N];
void init(){//000...~999...
	ten[0]=1;
	forr(i,1,N-1){
		dp[i]=i*ten[i-1];
		ten[i]=ten[i-1]*10;
	}
}
void calc(int x,int *cnt){
	int len=0;
	vector<int>num(15,0);
	while (x)
	{
		num[++len]=x%10;
		x/=10;
	}
	
	reforr(i,1,len){//从高到低位 假设为324
		//普通情况
		forr(j,0,9)cnt[j]+=num[i]*dp[i-1];// 0~299 后两位  0 1...num[i]-1
		forr(j,0,num[i]-1)cnt[j]+=ten[i-1];// 0~299 高位 
		//逼近情况
		int tp=0;
		forr(j,1,i-1)tp+=num[j]*ten[j-1];
		cnt[num[i]]+=(tp+1); //300~324 0~tp 共tp+1
		//去除前导零
		cnt[0]-=ten[i-1];
	}
	
}
void solve()
{
	init();
    int a,b;cin>>a>>b;
	calc(a-1,cnta),calc(b,cntb);
	forr(i,0,9)cout<<cntb[i]-cnta[i]<<' ';
}

记忆化搜索实现

const int N=16,INF=1e9+10;
int dp[N][N][2][2];
int now,num[N];
/*
pos:从高到低 处理到几位数字
sum:前面now的个数
lead:有无前导零
limit:有无数位限制
*/
int dfs(int pos,int sum,bool lead,bool limit){
	int ans=0;
	if(pos==0)return sum;
	if(dp[pos][sum][lead][limit]!=-1)return dp[pos][sum][lead][limit];

	int up=(limit?num[pos]:9);
	forr(i,0,up){//决定这一位是什么数
		if(i==0&&lead)ans+=dfs(pos-1,sum,1,limit&&i==up);
		else if(i!=now)ans+=dfs(pos-1,sum,0,limit&&i==up);//没有前导零
		else if(i==now)ans+=dfs(pos-1,sum+1,0,limit&&i==up);
	}

	dp[pos][sum][lead][limit]=ans;
	return ans;
}
int calc(int x){
	int len=0;
	while (x)
	{
		num[++len]=x%10;
		x/=10;
	}
	
	memset(dp,-1,sizeof dp);
	return dfs(len,0,1,1);//lead=true出0就是前导零了 limit&&k->k
}
void solve()
{
	int a,b;cin>>a>>b;
	forr(i,0,9)now=i,cout<<calc(b)-calc(a-1)<<' ';
}

P2657 Windy数

const int N=16,INF=1e9+10;
int dp[N][N][2][2];
int now,num[N];

/*
pos:从高到低 处理到几位数字
lst:最后一个数
lead:有无前导零
limit:有无数位限制
*/
int dfs(int pos,int lst,bool lead,bool limit){
	int ans=0;
	if(pos==0)return 1;
	if(dp[pos][lst][lead][limit]!=-1)return dp[pos][lst][lead][limit];

	int up=(limit?num[pos]:9);
	forr(i,0,up){//决定这一位是什么数
		if(abs(i-lst)<2)continue;
		if(i==0&&lead)ans+=dfs(pos-1,-2,1,limit&&i==up);//有前导零
		else ans+=dfs(pos-1,i,0,limit&&i==up);//没有前导零
	}

	dp[pos][lst][lead][limit]=ans;
	return ans;
}
int calc(int x){
	int len=0;
	while (x)
	{
		num[++len]=x%10;
		x/=10;
	}
	memset(dp,-1,sizeof dp);
	return dfs(len,-2,1,1);//-2是为了让最高位是任意数 lead=true出0就是前导零了 limit&&k->k
}
void solve()
{
	int a,b;cin>>a>>b;
	cout<<calc(b)-calc(a-1)<<endl;
}

P4124 手机号码

const int N=16,INF=1e9+10;
int dp[N][N][N][2][2][2][2];
int num[N];

/*
pos:从高到低 处理到几位数字
sec:倒数第二个数 lst:最后一个数 state:是否出现三连
et:8 fr:4
(不用考虑前导零)
limit:有无数位限制
*/
int dfs(int pos,int sec,int lst,bool state,bool et,bool fr,bool limit){
	int ans=0;
	if(et&&fr)return 0;
	if(pos==0)return state;
	if(dp[pos][sec][lst][state][et][fr][limit]!=-1)return dp[pos][sec][lst][state][et][fr][limit];

	int up=(limit?num[pos]:9);
	forr(i,0,up){//决定这一位是什么数
		ans+=dfs(pos-1,lst,i,state||(i==lst&&i==sec),et||(i==8),fr||(i==4),limit&&i==up);
	}

	dp[pos][sec][lst][state][et][fr][limit]=ans;
	return ans;
}
int calc(int x){
	int len=0;
	while (x)
	{
		num[++len]=x%10;
		x/=10;
	}
	if(len!=11)return 0;
	int ans=0;
	memset(dp,-1,sizeof dp);
	forr(i,1,num[len])ans+=dfs(len-1,0,i,0,i==8,i==4,i==num[len]);
	return ans;
}
void solve()
{
	int a,b;cin>>a>>b;
	cout<<calc(b)-calc(a-1)<<endl;
}

P2518 计数

题意：重新把所给的数各位排列组合，能得到多少更小的数
思路：可重复康托展开
康托展开速成

const int N=55,mod=1e9+7;
int c[N][N],sn[N],a[12];
int full_perm(int len){//全排列 len:剩下的位数
	int res=1;
	forr(i,0,9){
		res*=c[len][a[i]];
		len-=a[i];
	}
	return res;
}
void solve()
{
	string s;
	cin>>s;
	int len=s.size();
	forr(i,0,len-1){
		sn[i+1]=s[i]-'0';
		a[sn[i+1]]++;
	}
	//杨辉三角求组合数
	c[0][0]=1;
	forr(i,1,len){
		c[i][0]=c[i][i]=1;
		forr(j,1,i-1)c[i][j]=c[i-1][j-1]+c[i-1][j];
	}
	//开始展开
	int ans=0;
	forr(i,1,len){
		forr(j,0,sn[i]-1){//枚举比该位上小的数字
			if(a[j]){
				a[j]--;//让这一位上是j
				ans+=full_perm(len-i);//求全排列
				a[j]++;//还回来 继续定下一个数
			}
		}
		a[sn[i]]--;//题意让这一位≤n[i] 那就这一位上定死是n[i] 不然之后在全排列的时候 会重复
	}
	cout<<ans<<endl;
}