数位dp windy数

学习笔记

因为这题总是涉及相邻位，所以在计算的时候要多计算几个。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int n,m;
ll dp[15][15];
int a[15];
void init(){
	
	for(int i=0;i<=10;i++){
		dp[1][i]=1;
	}
	for(int i=2;i<=10;i++){
		for(int j=0;j<=9;j++){
			for(int k=0;k<=9;k++){
				if((abs(j-k)>=2)){//相邻 
					dp[i][j]+=dp[i-1][k];
				}
			}
		}
	}
}

ll dig(int x){
	int cnt=0;
	ll ans=0;
	do{
		a[++cnt]=x%10;
		x/=10;
	}while(x);
	a[cnt+1]=-1;
	
	for(int i=1;i<=cnt-1;i++){//除了最高位，其他数位的情况都无脑合法，因为我们是转移过来的
		for(int j=1;j<=9;j++){
			ans+=dp[i][j];
		}
	} 
	//因为windy数涉及高一位，但最高位没有高一位 
	for(int i=1;i<a[cnt];i++){//最高位最后一个数不能取，其他都i可以 
		ans+=dp[cnt][i];
	}
	
	for(int i=cnt-1;i>=1;i--){
		for(int j=0;j<a[i];j++){
			if(abs(j-a[i+1])>=2){
				ans+=dp[i][j];
			}
		}
		if(abs(a[i]-a[i+1])<2){//一次不合法，后面全部不合法 
			break;
		}
	} 
	
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	init();
	cin>>n>>m;
	cout<<dig(m+1)-dig(n)<<"\n";
	return 0;
}