【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1026

【题意】

【题解】



数位Dp

设f[i][j]表示长度为i,第一位(也就是最高位,注意不是个位数)为j的windy数的个数;

f[i][j] += ∑f[i-1][k] 这里abs(j-k)>1

这里f[1][0..9]都为0,这里的f[1][0]是为了后面的f[2][1..9]准备的.不然会漏掉20,30,….这些东西.

然后求A..B之间的Windy数;

可以转换为求

1..B之间的Windy数和1..A-1之间的Windy数;

相减就是答案了；

这里对于求1..x之间的windy个数;

设x的十进制长度为len;

则先加上

f[1..len-1][1..9]

然后对于len位数字的数.

可以一个一个枚举地加

注意细节问题就好.



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 110;

int A, B;

int a[N];

int dp[N][N];

void input_data()

{

    rei(A), rei(B);

}

void do_dp()

{

    rep1(i, 0, 9)

        dp[1][i] = 1;

    rep1(i, 2, 10)

        rep1(j, 0, 9)

            rep1(k, 0, 9)

                dp[i][j] += dp[i - 1][k] * (abs(j - k) > 1);

}

int get_ans(int x)

{

    int len = 0,cnt = 0;

    while (x)

    {

        a[++len] = x % 10;

        x /= 10;

    }

    rep2(i, len, 1)

    {

        if (i<len-1 && abs(a[i + 2] - a[i + 1]) <= 1) break;

        rep1(j, 0 + (i == len), a[i] + (i == 1) - 1)

            if (i==len||abs(a[i+1]-j)>1)

            {

                cnt += dp[i][j];

            }

    }

    rep1(i, 1, len - 1)

        rep1(j, 1, 9)

            cnt += dp[i][j];

    return cnt;

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    input_data();

    do_dp();

    printf("%d\n", get_ans(B) - get_ans(A - 1));

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}