[bzoj 1026]windy数[数位DP]

windy数的定义:

相邻两数位之间的差不小于2.
这个定义表明windy数的一部分一也是windy数.

较长的windy数与较短的windy数之间的关系:

当较短的数是windy数时,只要考虑加的那一位和最高位之间的差是否大于1.
最高位.

于是可设计状态:

dp[i][j]----有i位的数中,最高位为j的windy数的个数.

状态转移方程:

dp[i][j] += dp[i-1][k]( k = 0..9 && |j-k| < 2)

预处理是考虑首位为0的情况的,因为用它的时候它常常不是首位.计算的时候避免即可.

计算结果:

这个时候必须分开算.不足len位的情况要累加.因为此时不考虑先导0.
如果像Bomb那道题一样直接并入最高位的计算的话就考虑了先导0.

len位数的计算就仿照Bomb了.

仍然注意:

从高位到低位,讨论的数逐渐增大逼近上界,当某一位固定为子串最高位时(即与原数的该位相同时)

若恰好违背windy数,那么计算终止.因为此位已经是最大的了,而以此位为最高位的所有数都非法,

也就是说此后直到上界,都不可再增加,因此计数终止.

//808 kb	0 ms
#include <cstdio>
using namespace std;
const int MAXN = 12;
typedef long long ll;
ll dp[MAXN][10];
int bit[MAXN];
int len;
int abs(int x)
{
    return (x + (x>>31))^(x>>31);
}
void InitDP()
{
    for(int i=0;i<10;i++)        dp[1][i] = 1;
    for(int i=2;i<MAXN;i++)
        for(int j=0;j<10;j++)
            for(int k=0;k<10;k++)
                if(abs(j-k)>1) dp[i][j] += dp[i-1][k];
}
void pre(int x, int &len)
{
    int i;
    for(i=1; x; i++)
    {
        bit[i] = x % 10;
        x /= 10;
    }
    bit[i] = 0;
    len = i-1;
}
ll cal(int x)
{
    ll ret = 0;
    for(int i=1;i<len;i++)
        for(int j=1;j<10;j++)
            ret += dp[i][j];
    for(int i=1;i<bit[len];i++)
        ret += dp[len][i];
    for(int i=len-1; i; i--){
        for(int j=0;j<bit[i];j++)
            if(abs(bit[i+1]-j)>1)   ret += dp[i][j];
        if(abs(bit[i+1]-bit[i])<2)  break;
    }
    return ret;
}
int main()
{
    int a,b;
    InitDP();
    while(scanf("%d %d",&a,&b)==2)
    {
        ll ansa,ansb;
        pre(a,len);
        ansa = cal(a);
        pre(++b,len);
        ansb = cal(b);
        printf("%lld\n",ansb-ansa);
    }
}

补充：综合编程 , 其他综合 ,