八段第四课：数位DP

A包含49的数字

解法

我们可以使用记忆化搜索从高到低一位一位放，每位都从 $0-9$ 枚举，使用数组优化。

设 $f_{i,0/1/2}$ 表示从高到低第 $i$ 为的三种情况：

  1. $0$ ，表示前面出现过 $49$.
  2. $1$，表示前面没出现过 $49$。
  3. $2$，表示前面没出现过 $49$，但是以 $4$ 结尾。

那么我们就可以直接转移。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define int long long
//0: 有49 1：没49 2：以4开头 
long long n;
long long dp[123][123];
int w[123];
long long dfs(int pos,int mask,int limt)//当前位数，状态，能选到的极限（0表示能选到0~9，1则表示能选0~a[pos]）
{
	if(pos==0) return mask==0;//搜到，返回一个方案数。
	if(!limt && dp[pos][mask]!=-1) return dp[pos][mask];//记忆化搜索的返回，注意要保证limt不为1
	int x=(limt==1?w[pos]:9);
	long long ret=0;
	for(int i=0;i<=x;i++)
	{
		int nm=mask;
		if (mask==0) nm=0;//有49，随便转移
		else if (i==4) nm=2;//以4结尾
		else if (mask==2 && i==9) nm=0;//前面有4，怎么拼上一个9变成了状态0
		else nm=1;
		ret+=dfs(pos-1,nm,limt&(i==x));
	}
	if(!limt) dp[pos][mask]=ret;//要保证limt不为1，这样就不需要考虑边界情况了，能用的时候直接用。
	return ret;
}
void solve(int u)
{
	int tot=0;
	while(u>0) w[++tot]=u%10,u/=10;
	int l=1,r=tot;

	cout<<dfs(tot,1,1)<<endl;
}
signed main()
{
    while(scanf("%lld",&n)==1)
    {
        memset(dp,-1,sizeof dp);
	    solve(n);
    }
	
}

B 书面零计数

解法

可以使用数位 $dp$。

跟上题一样，我们可以使用记忆化搜索。设 $f_{i,j}$ 表示已经填了 $i$ 位，前面出现了 $j$ 个 $0$ 的方案数。

然后直接枚举就行了，注意还需要一个变量判断目前是否是前导零。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int w[33];
int dp[33][33];

int dfs(int pos,int lim,int cnt,int qdl)
{
	if(pos==0) return cnt;
	if(dp[pos][cnt]!=-1 && !qdl && !lim) return dp[pos][cnt];
	int x=lim?w[pos]:9;
	int ret=0;
	for(int i=0;i<=x;i++)
	{
		int t=cnt;
		if(i==0 && !qdl) t++;
		ret+=dfs(pos-1,lim&&(i==x),t,qdl&&(i==0));
	}
	if(!lim && !qdl) dp[pos][cnt]=ret;
	return ret;
}
int solve(int n)
{
	if(n==-1) return -1;
    memset(dp,-1,sizeof dp);
	int tot=0;
	while(n>0) w[++tot]=n%10,n/=10;
	return dfs(tot,1,0,1);
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	
	cout<<solve(m)-solve(n-1)<<endl;
}