【BZOJ1026】windy数，数位DP

Time:2016.08.14
Author:xiaoyimi
转载注明出处谢谢

---

思路：
依旧蛋疼的数位DP
f[i][j]表示有i位，且最高位为j的windy数个数
转移方程比较好写
关键是具体求值的时候不太好弄
从小位往高位求
cal(i)实际上算出的是1~i-1的windy数
所以判断一下i是否为windy数就可以了
代码：

#include<cstdio>
using namespace std;
int a,b;
int f[11][10],num[11];
int ab(int x){return x>=0?x:-x;}
bool check(int x)
{
    if (!x) return 0;
    int last=x%10;
    x/=10;
    for (;x;last=x%10,x/=10)
        if (ab(x%10-last)<2) return 0;
    return 1;
}
int cal(int x)
{
    num[0]=0;
    int last,ans=0,k=x;
    num[++num[0]]=k%10;k/=10;
    for (;k;k/=10) num[++num[0]]=k%10;
    for (int i=1;i<num[0];i++)
        for (int j=1;j<=9;j++)
            ans+=f[i][j];
    for (int i=1;i<num[num[0]];i++)
        ans+=f[num[0]][i];
    last=num[num[0]];
    for (int i=num[0]-1;i;last=num[i],i--)
    {
        for (int j=0;j<num[i];j++)
            if (ab(last-j)>=2) ans+=f[i][j];
        if (ab(last-num[i])<2) break;
    }
    return ans+check(x);
}
main()
{
    for (int i=0;i<=9;i++) f[1][i]=1;
    for (int i=2;i<=10;i++)
        for (int j=0;j<=9;j++)
            for (int k=0;k<=9;k++)
                if (ab(j-k)>=2)
                    f[i][j]+=f[i-1][k];

    scanf("%d%d",&a,&b);
    printf("%d",cal(b)-cal(a-1));
}