【BZOJ 1026】[SCOI2009] windy数

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1026

数位DP

#include<iostream>
#include<cstdio>
#include<cstring>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 20;

int f[MAXN][MAXN],a,b;

inline void prework(){
	for (int i=0;i<=9;i++) f[1][i] = 1;
	for (int k=2;k<=10;k++) {
		for (int i=0;i<=9;i++) {
			for (int j=i+2;j<=9;j++) f[k][i] += f[k-1][j];
			for (int j=i-2;j>=0;j--) f[k][i] += f[k-1][j];
		}
	}
}

inline int cal(int w){
	int tot=0,arr[MAXN],ret=0;
	memset(arr,0,sizeof(arr));
	while (w) arr[++tot] = w % 10, w /= 10;
	
	for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j];
	for (int i=1;i<arr[tot];i++) ret += f[tot][i];
	for (int i=tot-1;i>0;i--) {
		for (int j=0;j<=arr[i]-(i==1?0:1);j++)if (abs(j-arr[i+1]) >= 2) ret += f[i][j];
		if (abs(arr[i]-arr[i+1]) < 2) break;
	}
	return ret+(tot==1);
}

int main(){
	prework();
	scanf("%d%d",&a,&b); 
	printf("%d",cal(b)-cal(a-1));
	return 0;
}