传送门：?id=1026
数位dp果断记忆化搜索，，代码量少~ 程序里我用11代表前导零。
#include <cstdio> #include <cstring> int A, B, f[15][15][2], a[15], wei; inline int abs(int aa) { return aa > 0? aa: -aa; } int dp(int left, int now, char jin) { if (f[left][now][jin] != -1) { return f[left][now][jin]; } if (!left) { return f[left][now][jin] = 1; } int & rhs = f[left][now][jin]; rhs = 0; if (jin) { if (abs(a[left] - now) >= 2) { rhs += dp(left - 1, a[left], 1); } for (int i = 0; i < a[left]; ++i) { if (abs(i - now) >= 2) { rhs += dp(left - 1, i, 0); } } } else if (now == 11) { rhs += dp(left - 1, 11, 0); for (int i = 1; i < 10; ++i) { rhs += dp(left - 1, i, 0); } } else { for (int i = 0; i < 10; ++i) { if (abs(i - now) >= 2) { rhs += dp(left - 1, i, 0); } } } return rhs; } inline int slove(int n) { if (n < 10) { return n + 1; } wei = 0; while (n) { a[++wei] = n % 10; n /= 10; } memset(f, -1, sizeof f); int rt = dp(wei - 1, 11, 0); for (int i = 1; i < a[wei]; ++i) { rt += dp(wei - 1, i, 0); } rt += dp(wei - 1, a[wei], 1); return rt; } int main(void) { scanf("%d%d", &A, &B); printf("%d\n", slove(B) - slove(A - 1)); return 0; }
_bzoj1026 [SCOI2009]windy数【数位dp】