传送门

f[i][j]表示位数为i，第i位为j的windy数的个数

先预处理出f数组。

求的时候先算没有前导0的答案，再算位数和给定的数相同的答案。

#include
#include
#include

using namespace std;

int f[15][10], d[15];

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

inline int query(int x)
{
int i, j, ret = 0;
memset(d, 0, sizeof(d));
for(; x; x /= 10) d[++d[0]] = x % 10;
for(i = 1; i < d[0]; i++) for(j = 1; j <= 9; j++) ret += f[i][j]; for(i = d[0]; i >= 1; i--)
{
for(j = 0; j < d[i]; j++) { if(i == d[0] && !j) continue; if(i == d[0]) ret += f[i][j]; else if(abs(d[i + 1] - j) >= 2) ret += f[i][j];
}
if(i != d[0] && abs(d[i + 1] - d[i]) < 2) break;
}
return ret;
}

int main()
{
int l, r;
init();
scanf("%d %d", &l, &r);
printf("%d\n", query(r + 1) - query(l));
return 0;
}