HYSBZ:1026 windy数(数位DP)

题意：求区间内windy数的个数。

思路：数位DP。用递归比较好写。

设f[cur][num]表示当前是第cur位，第cur+1位的数字是num时的windy数个数。

显然状态转移方程是f[cur][num]=sum{f[cur-1][i]}(abs(num-i)>=2)。

注意处理前导零。

另外像1，2，3这种个位数也windy数。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int digits[15];
int f[12][15];
//f(i,j)表示当前是第i位，第i+1位是j时的个数
int dp(int cur,int num,bool isFirst,bool isEnd)
{
    if(cur==-1)
    {
        if(isFirst) return num!=0;
        else return 1;
    }
    if(!isFirst&&!isEnd&&f[cur][num]!=-1)
        return f[cur][num];
    int ans=0;
    int ed=isEnd?digits[cur]:9;
    for(int i=0; i<=ed; ++i)
    {
        if(isFirst)
            ans+=dp(cur-1,i,isFirst&&i==0,i==ed&&isEnd);
        else if(abs(num-i)>=2)
            ans+=dp(cur-1,i,false,i==ed&&isEnd);
    }
    if(!isFirst&&!isEnd)
        f[cur][num]=ans;
    return ans;
}
int solve(int x)
{
    if(x==0) return 0;
    int len=0;
    while(x)
    {
        digits[len++]=x%10;
        x/=10;
    }
    memset(f,-1,sizeof(f));
    return dp(len-1,0,true,true);
}
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
        printf("%d\n",solve(b)-solve(a-1));
    return 0;
}