[SCOI2009]windy数

BZOJ1026..
 
写完这道题感觉心好累...这辈子都不想再做数位DP的题了,然而他们说这是道入门题...
首先可以DP得到位数为i,最高位为j的windy数个数g(i,j)
然后对于(0,k)内的windy数个数,可以讨论3种情况:(感觉数位DP就是大讨论..)
(假设总位数为l,假设k的从高到低第t位为bit(t) )
①最高位为0,位数为[1,l - 1]的windy数个数(Σ(q=1,l-1) Σ(p=1,9) g(p,q))
②最高位为[1,k - 1],位数为l的windy数个数(Σ(q=1,k-1) g(l,q))
③最高位为k的windy数个数,这个比较复杂,总之是从高位到低位依次确定,伪代码如下:
for i = (len - 1) to 1 , step -1:
  for q = 1 to bit(i) - 1 (#) , step 1: 
   if(|q - bit(i + 1)| > 2)
     sum <- sum + g(i,q)
   endif
  endfor
endfor
 
注意打#的地方,这里取bit(i) - 1是因为求的是开区间(闭区间的话会麻烦一点)
 
完整代码如下:

#include <stdio.h>

#include <string.h>

#include <iostream>

 

typedef long long Long;

 

Long g[20][20];//g[i][j] : i位开头为j的windy数个数 

 

Long ABS(Long a)

{

    return a > (Long)0 ? a : -a;

}

 

void init()

{

    for(Long i = 0;i < 10;i++)

        g[1][i] = 1LL;

     

    for(Long i = 2;i <= 10;i++)

    {

        for(Long j = 0;j < 10;j++)

        {

            for(Long k = 0;k < 10;k++)

            {

                if(ABS(j - k) >= 2)

                    g[i][j] += 1LL * g[i - 1][k];

            }

        }

    }

}

 

Long bit[20];

Long len = 0;

Long get_res(Long k)//(0,k)

{

    memset(bit,0,sizeof(bit));

 

    len = 0;

     

    Long q = k;

    while(q)

    {

        bit[++len] = (q % 10LL);

        q /= 10LL;

    }

     

    Long result = 0;

     

    /*

        000x

        00xx

        0xxx...

    */

    for(Long i = 1;i < len;i++)

    {

        for(Long j = 1;j < 10LL;j++)

        {

            result += 1LL * g[i][j];//开头不可为0 

        }

    }

     

    /*

        1xxx

        2xxx

        3xxx

        .

        .

        (a-1)xxxx

    */

    for(Long i = 1;i <= bit[len] - 1;i++)

    {

        result += g[len][i];

    }

     

    /*

    a [0,b)[0,c)[0,d)...

    */

    for(Long i = len - 1;i >= 1;i--)

    {

        for(Long j = 0;j < bit[i];j++)//枚举第i位 

        {

            if(ABS(bit[i + 1] - j) >= 2LL)

                result += g[i][j];

        }

         

        if(ABS(bit[i] - bit[i + 1]) < 2LL)

            break;

    }

     

    return result;

}

 

int main()

{

     

    init();

     

    Long l = 0LL;

    Long r = 0LL;

     

    std::cin>>l>>r;

     

    Long result = get_res(r + 1LL) - get_res(l);

     

    //for(int i = 0;i <= 10;i++)

    //  for(int j = 0;j < 10;j++)

    //      std::cout<<i<<" "<<g[i][j]<<"\n";

            //printf("%d %d\n",i,g[i][j]);

     

    std::cout<<result<<std::endl;

     

    return 0;

}