[SCOI 2009] Windy数

题目描述：

如果一个数字相邻位上的数差的绝对值都>=2，称这个数为Windy数

现在给出一段区间，求这个区间里的Windy数数量

题目分析：

利用前缀和思想 我们可以计算出[1 - r]的Windy数 数量 减去 [1-(l-1)]的Windy数 数量…

预处理数组 dp[i][j]表示有i为最高位为j的Windy 数 数量

初始化 dp[1][1-9]=1

转移显然 枚举数位 枚举当前数位的数 枚举上一位数位的数 判断是否符合条件 然后转移…

我们对于一个被查询的数拆开 处理…

设拆完的数有len位，从低位到高位放到 a[1],a[2]…a[len]

首先先统计比查询的数少一位的Windy数数量 注意不可以有前导0

for(int i=;i<len;i++) 
     for(int j=;j<=;j++)
      ans+=dp[i][j];
           

然后统计位数一样 但是最高位比查询的数小的Windy数数量 也不可以有前导0

for(int i=;i<=a[len]-;i++)
     ans+=dp[len][i];
           

最后统计最高位为查询数的Windy数数量 由于最高位已经确定不是 0 ，所以枚举答案的时候可以加上 0

for(int i=len-;i>=;i--)
    {
        for(int j=;j<a[i];j++)
         if(abs(j-a[i+])>=) ans+=dp[i][j];
        if(abs(a[i+]-a[i])<=) break;
    }
           

这样我们求出的是小于 x 的Windy数个数 所以答案为slove(r+1)-slove(l)

感觉数位DP就是预处理一个数组，然后卡位讨论

题目链接：

BZOJ 1026

Luogu 2657

Ac 代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
int dp[][];
int a[];
inline int abs(int x){return x<?-x:x;}
inline void pre()
{
    for(int i=;i<=;i++)
     dp[][i]=;
    for(int i=;i<=;i++)
     for(int j=;j<=;j++)
     {
        for(int k=;k<=;k++)
        if(abs(j-k)>=) dp[i][j]+=dp[i-][k];
     }
}
inline int slove(int n)
{
    int len=;
    while(n) a[++len]=n%,n/=;
    a[len+]=;
    int ans=;
    for(int i=;i<len;i++) 
     for(int j=;j<=;j++)
      ans+=dp[i][j];
    for(int i=;i<=a[len]-;i++)
     ans+=dp[len][i];
    for(int i=len-;i>=;i--)
    {
        for(int j=;j<a[i];j++)
         if(abs(j-a[i+])>=) ans+=dp[i][j];
        if(abs(a[i+]-a[i])<=) break;
    }
    return ans;
}
int main()
{
    pre();
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",slove(r+)-slove(l));
    return ;
}