UESTC 250

windy数

基本的数位DP，需要判断当前位是否为起始位。

#include <cstdio> #include <cmath> #include <cstring> using namespace std;#define D(x) xconst int MAX_DIGIT = 35;int n, m; int f[MAX_DIGIT]; int memoize[MAX_DIGIT][2][2][15];void to_digits(int a) {for (int i = 0; i < MAX_DIGIT; i++){f[i] = a % 10;a /= 10;} }int dfs(int digit, bool less, bool first, int last) {if (digit == -1){return 1;}if (memoize[digit][less][first][last] != -1){return memoize[digit][less][first][last];}int limit = less ? 9 : f[digit];int ret = 0;for (int i = 0; i <= limit; i++){if (!first && abs(i - last) < 2){continue;}ret += dfs(digit - 1, less || i < f[digit], first && i == 0, i);}memoize[digit][less][first][last] = ret;return ret; }int main() {scanf("%d%d", &n, &m);n--;to_digits(n);memset(memoize, -1, sizeof(memoize));int ans_n = dfs(32, false, true, 12);to_digits(m);memset(memoize, -1, sizeof(memoize));int ans_m = dfs(32, false, true, 12);printf("%d\n", ans_m - ans_n);return 0; } View Code

 

总结

以上是生活随笔为你收集整理的UESTC 250的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。