BZOJ 1026 Windy数字

发表于 | 更新于

Link

Solution

数位DP模板？

然而有一点需要注意：长度不足nn的必须单独算(或者我没想出好办法？)

想了很长时间想巧妙地避免分开处理，发现不好避免。

所以数位DP就可以类比AC自动机DP，可以把长度小于给定串的单独处理。

Code

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
#include "lucida"

int f[15][10];
void DP() {
	for(int i=0;i<10;++i)
		f[1][i]=1;
	for(int i=1;i<=10;++i)
		for(int j=0;j<10;++j)
			for(int k=0;k<10;++k)
				f[i][j]+=(abs(j-k)>=2)*f[i-1][k];
				//j==0? is that right?
}
int Cute(int x) {
	static int bit[15],len;
	//if(x==0) return 0;
	for(len=0,++x;x;x/=10)
		bit[++len]=x%10;
	bit[len+1]=2333;
	int res=0;
	for(int i=len-1;i;--i)
		for(int j=1;j<10;++j)
			res+=f[i][j];
	for(int i=len;i;--i) {
		for(int j=(i==len);j<bit[i];++j)
			res+=(abs(bit[i+1]-j)>=2)*f[i][j];
		if(abs(bit[i+1]-bit[i])<2)
			break;
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	DP();
	int l,r;
	is>>l>>r;
	os<<(Cute(r)-Cute(l-1))<<'\n';
	return 0;
}