BZOJ 1026: [SCOI2009]windy数

2021-07-17 18:19

阅读:1546

标签:max   post   数字   ble   php   zoj   lin   efi   div   

二次联通门 : BZOJ 1026: [SCOI2009]windy数

 

 

 

/*
    BZOJ 1026: [SCOI2009]windy数

    水题开心
    数位dp
    f[i][j]表示一个i位的数字的第i位是j的数字有几个

    设 s (x)为[0,x)的答案
    怎么求s(x)?
    设x有t位,我们先找到所有t - 1的符合题意的数
    然后从高到低一位一位得确定为原数字x对应位上的数字
    在此基础上累计方案数就好了
    就能求出[0,x)的答案了
    然后s (M + 1) - s (N)即可
*/
#include #define rg register
#define Max 20
int f[Max][Max], d[Max];
inline int abs (int x) { return x 0 ? -x : x; }
int Calc (int x)
{
    int c = 0, res = 0; rg int i, j, k;
    for (; x; d[++ c] = x % 10, x /= 10);
    for (i = 1; i  i)
        for (j = 1; j 9; ++ j) res += f[i][j];
    for (i = c; i; -- i)
    {
        for (j = (i == c); j  j)
            if (i == c || abs (j - d[i + 1]) >= 2)
                res += f[i][j];
        if (i 1] - d[i]) 2) break;
    }
    return res;
}
int main (int argc, char *argv[])
{
    rg int i, j, k;
    for (i = 0; i 9; ++ i) f[1][i] = 1;
    for (i = 1; i 10; ++ i)
        for (j = 0; j 9; ++ j)
        {
            for (k = 0; k 2; ++ k) f[i + 1][k] += f[i][j];
            for (k = j + 2; k 9; ++ k) f[i + 1][k] += f[i][j];
        }
    int N, M;
    scanf ("%d%d", &N, &M);
    printf ("%d", Calc (M + 1) - Calc (N));

    return 0;
}

 

BZOJ 1026: [SCOI2009]windy数

标签:max   post   数字   ble   php   zoj   lin   efi   div   

原文地址:https://www.cnblogs.com/ZlycerQan/p/8127816.html


评论


亲,登录后才可以留言!