首页 > 代码库 > UESTC 250

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