f[i][j]暗示位数为i，，第i位为j的windy数的个数
先预措置惩罚惩罚出f数组。
求的时候先算没有前导0的答案，再算位数和给定的数不异的答案。
#include <cmath> #include <cstdio> #include <cstring> 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; }