P2657

在题解界面里 LaTeX 可能会挂，请去 博客 里查看。

预处理（状态）

设 $f_{i,j}$ 表示第 $i$ 位（个位为第 $1$ 位）的数字是 $j$ 的 $i$ 位数中，有多少 windy 数。

例如，$f_{3,5}$ 表示 $[500,600)$ 中 windy 数的个数。

那如何计算 $f_{3,5}$ 呢？

$$500\sim599=\begin{cases} 500\sim509\implies00\sim09=f_{2,0}\\ 510\sim519\implies10\sim19=f_{2,1}\\ 520\sim529\implies20\sim29=f_{2,2}\\ 530\sim539\implies30\sim39=f_{2,3}\\ \xcancel{540\sim549}\\ \xcancel{550\sim559}\\ \xcancel{560\sim569}\\ 570\sim579\implies70\sim79=f_{2,7}\\ 580\sim589\implies80\sim89=f_{2,8}\\ 590\sim599\implies90\sim99=f_{2,9}\\ \end{cases}$$

注意到 $540\sim560$ 中没有 windy 数。

易证 $500\sim509$ 中的 windy 数和 $00\sim09$（包括前导 0）中的 windy 数一一对应，其他同理。

于是写出代码：

for(int i=0;i<10;i++) f[1][i]=1;//1 位数都是 windy 数
//特殊地，0 位数即 0，也可以被认为是 windy 数（虽然不满足定义）
for(int i=2;i<=10;i++)//枚举位数
	for(int j=0;j<10;j++)//枚举第 i 位的数
		for(int k=0;k<10;k++)//枚举第 i-1 位的数
			if(abs(j-k)>1)//如果差大于等于 2
				f[i][j]+=f[i-1][k];//累加上

计算 I

$l\sim r$ 的 windy 数不好求，可以将 $0\sim r$ 中 windy 数的个数减去 $0\sim l-1$ 中 windy 数的个数求得。于是定义 $g_i$ 函数，表示 $0\sim i$ 中 windy 数的个数。

例如，如何计算 $g_{2451}$呢？

$$g_{2451}=\begin{cases} 0\sim1999\\ 2000\sim2399\\ 2400\sim2449\\ 2450\sim2450 \end{cases}$$

等等，最后一个不是 $2450\sim2451$ 吗？
观察前几个范围，发现都是到该位少 $1$，而个位单独特判一下比较麻烦，所以更改定义：$g_{i}$ 表示 $0\sim i-1$ 中 windy 数的个数。

继续：

$$0\sim1999=\begin{cases} 0\sim999=f_{4,0}\\ 1000\sim1999=f_{4,1} \end{cases}$$

上式对吗？不对！

还记得 $f_{3,0}$ 表示的是 $0000\sim0999$ 中 windy 数的个数吗？这是带前导 0 的，而要求的不能带前导 0。
比如 $1$ 是 windy 数，而 $0001$ 不是。

怎么办呢？我们定义一个 $s$ 函数。

$s$ 函数

$s_i$ 表示 $0\sim10^i-1$（不带前导 0）中 windy 数的个数。

例如 $s_3$：

$$0\sim999=\begin{cases} 0\sim99=s_2\\ 100\sim199=f_{3,0}\\ 200\sim299=f_{3,1}\\ \cdots\\ 900\sim999=f_{3,9} \end{cases}$$

$s$ 函数可以在计算 $f$ 的时候同时计算出来：

sum[0]=1; sum[1]=10;//这俩要提前算
for(int i=2;i<=15;i++){
	for(int j=0;j<10;j++)
		for(int k=0;k<10;k++)
			if(abs(j-k)>1)
				f[i][j]+=f[i-1][k];
	sum[i]=sum[i-1];
	for(int j=1;j<10;j++) sum[i]+=f[i][j];
}

计算 II

回来继续算 $g_{2451}$。

$$g_{2451}=\begin{cases} 0\sim1999=\begin{cases} 0\sim999=s_3\\ 1000\sim1999=f_{4,1} \end{cases}\\ 2000\sim2399=\begin{cases} 2000\sim2099\implies000\sim099=f_{3,0}\\ \xcancel{2100\sim2199}\\ \xcancel{2200\sim2299}\\ \xcancel{2300\sim2399} \end{cases}\\ 2400\sim2449=\begin{cases} 2400\sim2409\implies00\sim09=f_{2,0}\\ 2410\sim2419\implies10\sim29=f_{2,1}\\ 2420\sim2429\implies10\sim29=f_{2,2}\\ \xcancel{2430\sim2439}\\ \xcancel{2440\sim2449} \end{cases}\\ \xcancel{2450\sim2450} \end{cases}$$

大概都是能看懂的，这里说一下最后一行：因为十位和百位差小于 $2$，所以整个都弃掉了。所以一旦发现相邻两位差小于 $2$，直接跳出不再算。

思路了解了，就要写代码了：

int work(int x){
	int cnt=0,ans=0;//cnt 是 x 的位数，ans 记录答案
	for(;x;x/=10) a[++cnt]=x%10;//将 x 的各位存到数组里，方便处理
	ans+=sum[cnt-1];//这行和下一行计算最高位
	for(int i=1;i<a[cnt];i++) ans+=f[cnt][i];
	for(int i=cnt-1;i;i--){//计算剩余每位
		for(int j=0;j<a[i];j++)
			if(abs(j-a[i+1])>1) ans+=f[i][j];
		if(abs(a[i+1]-a[i])<2) break;//如果差小于2，跳出
	}
	return ans;
}

完整代码

#include<iostream>
#include<cmath>
using namespace std;
int lft,rght,f[20][20],sum[20],a[20];
int work(int x){
	int cnt=0,ans=0;
	for(;x;x/=10) a[++cnt]=x%10;
	ans+=sum[cnt-1];
	for(int i=1;i<a[cnt];i++) ans+=f[cnt][i];
	for(int i=cnt-1;i;i--){
		for(int j=0;j<a[i];j++)
			if(abs(j-a[i+1])>1) ans+=f[i][j];
		if(abs(a[i+1]-a[i])<2) break;
	}
	return ans;
}
int main(){
	cin>>lft>>rght;
	for(int i=0;i<10;i++) f[1][i]=1;
	sum[0]=1; sum[1]=10;
	for(int i=2;i<=15;i++){
		for(int j=0;j<10;j++)
			for(int k=0;k<10;k++)
				if(abs(j-k)>1)
					f[i][j]+=f[i-1][k];
		sum[i]=sum[i-1];
		for(int j=1;j<10;j++) sum[i]+=f[i][j];
	}
	cout<<work(rght+1)-work(lft)<<endl;
	return 0;
}

E37 数位DP Windy数

#include<bits/stdc++.h> //by: hansang.Vargas
using namespace std;
typedef long long LL;
const int N=30;
LL f[N][15], a[15];
LL calc(LL x){
    int len=0; LL last=-2, ans=0; 
    //last是上一位，初始为-2，这样最高位合法 
    while(x>0) a[++len]=x%10, x/=10;
    for(int i=len; i>=1; i--){
        for(int j=(i==len? 1: 0); j<a[i]; j++){ 
            //len位不能有前导零
            if(abs(j-last)>=2) ans+=f[i][j]; //合法就加
        }
        if((abs(a[i]-last)<2)) break; 
        //因为当前计算都是建立在a数组上的，所以不合法的话下一步便不符合定义
        last=a[i];
        if(i==1) ans++; //x本身
    }
    for(int i=len-1; i>=1; i--) //没有到最高位
        for(int j=1; j<=9; j++) //这个时候是严格的i位数字
            ans+=f[i][j];
    return ans;
}
int main(){
    //freopen("a.in", "r", stdin);
    memset(f, 0, sizeof(f));
    for(int i=0; i<=9; i++) f[1][i]=1;
    for(int t=2; t<=25; t++){
        for(int i=0; i<=9; i++){
            for(int j=0; j<=9; j++) if(abs(i-j)>=2)
                f[t][i]+=f[t-1][j]; //dp windy数
        }
    }
    LL a, b; scanf("%lld%lld", &a, &b);
    LL x=calc(b), y=calc(a-1);
    printf("%lld\n", x-y);
    return 0;
}