bzoj1026 [SCOI2009]windy数 数位dp

    定义windy数是没有前导零且相邻两位数字只差大于等于2的数，查询【A,B】之间有多少个windy数..

dp的时候要特殊考虑下当前位以上全是0的情况，所以加一维状态，dp[pos][st][pre]表示第pos位，高一位的值是st，高位是否全为0时有多少个符合要求的数。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int dp[33][11][2];
int num[33];

int f(int pos,int st,bool limit,bool pre)
{
    if (pos==-1) return 1;
    if (!limit && dp[pos][st][pre]!=-1) return dp[pos][st][pre];
    int ans=0;
    int last=limit?num[pos]:9;
    for (int i=0; i<=last; i++)
    {
        if (abs(i-st)>=2 || (st==0&& pre) )
        {
            ans+=f(pos-1,i,limit&&i==last,pre&&(i==0) );
        }
    }
    if (!limit) dp[pos][st][pre]=ans;
    return ans;
}
int cal(int x)
{
    if (x==0) return 1;
    int len=0;
    int ans=0;
    while(x)
    {
        num[len++]=x%10;
        x/=10;
    }
    for (int i=0; i<=num[len-1]; i++)
    {
        ans+=f(len-2,i,i==num[len-1],i==0);
    }

    return ans;
}
int n,m;
int main()
{

    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,-1,sizeof dp);
//        cout<<cal(m)<<endl;
//        cout<<cal(n-1)<<endl;
        cout<<cal(m)-cal(n-1)<<endl;
    }
    return 0;
}