題目描述：
如果一個數字相鄰位上的數差的絕對值都>=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 ;
}